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.