The pathfinding algorithm has been decently optimized. The reality is that 600 units finding paths and keeping them up to date is a lot of work.
Some of the pathfinding is precomputed, some cannot be as it involves other units and formations.
Most other RTS games work around this by either relaxing the constraints or implement some amount of parallelism.
There is also some exciting work going on to improve the path finding of formations to make them behave more naturally: https://gitea.wildfiregames.com/0ad/0ad/pulls/8608
A realistic version would have unit commanders pathfinding over long distance, and the plebs following them unless they got merc'ed
I think this actually can be used to optimize the pathfinding. Basically create a fake unit that is used for the real/complex path, then have the other units follow it with basic collision or a very tuned down pathfinding algorithm similar to the hack I did where I just counted loop iterations and bailed after some threshold.