How to set up grids for a large RTS generated terrain?

I’m started working on an RTS game with a large terrain. Actually I generate terrain tiles with a dimension of 1000×1000 and a height level of 300. Those tiles are generated by the MapMagic procedural terrain generator on level startup, actually I will limit the terrain level based on 10×10 tiles.

There should be exist multiple fractions (AI and Multiplayer) with multiple units which requires pathfinding to move. Also the terrain will be modified to set up settlements and infrastructure (roads ect). What is the best way to handle such a huge terrain with an option to travel long distances?