When you mention render submission being the main bottleneck, is the core issue that Pyrogenesis's rendering pipeline runs sequentially on a single CPU thread, or is it already multithreaded and just struggling with massive draw call volume late-game? Furthermore, is there any prospect for optimization through GPU instancing to batch identical units and cut down those draw calls?
Pathfinding is not actually as performance expensive as one would think. The individual pathfinding requests each turn can be (and are) nicely computed in parallel by the engine, so on machines with decent hardware concurrency they finish surprisingly fast. The render submission process and rendering itself are a much more perfomance-constraining factor.