Run the gameplay profiler UDK | GameplayProfiler to see what is taking the most time. It might be the AIControllers running every tick.
My game Himeko Sutori runs fine with 400 pawns in each battle, but my game is turn-based, and you never have more than 20 pawns active at any time, so I only need 20 AIControllers. The 20 AIControllers possess different pawns when it’s time for those pawns to act.
If you don’t actually need 500 gladiators working as fully capable bots, then maybe you should look into crowds UDK | CrowdSystem or some kind of simple actor that has a skeletal mesh component.