I'm also working with Unreal Engine and using Perforce for revision control. I seem to have exactly the same issue. Operations on up to a few thousand files at once are very fast, but operations on 10k or more files start taking minutes to hours to complete, in the worst cases I've had to leave operations to run overnight for 10+ hours. What seems to be happening is that there's something like an N^2 relationship between the number of files and the operation time, even though I would expect the relationship to be linear (reconcile for example doesn't need to compare each file, just each file to its version in the depot). As far as I can tell so far it's not due to the server's resources or network conditions.

As a workaround, I recommend doing large operations piecemeal, one subset of files at a time. It's much faster to submit or reconcile 10 folders of 10k files each than it is to submit or reconcile one folder of 100k files, for example.