Have you tried this with a recent version? Version 4.2 improved the performance of graph updates on very large graphs significantly. In 4.2+ pathfinding performance should only be affected in rare cases when a path has to search the whole graph. This can happen if you are using tags and the end node of a path is not reachable from the start node using the allowed tags.
Relevant changelog quote:
Improved performance of small graph updates on large graphs by a very large amount. Previously when making a small update to a large graph, updating the connected components of the graph using a flood fill has been the thing which took the longest time by far. Using a new internal hierarchical graph it is now possible to update large graphs much faster. For example making a small update to a 1024*1024 grid graph is on the order of 30 times faster and is now perfectly reasonable to do in real time (slightly depending on how the graph looks and its settings). The cost of the flood fill was previously offloaded to a separate thread, so it would not always be noticed in the Unity profiler, but it was there and could affect the performance of the game in strange ways. The performance of scanning a graph or updating the whole graph remains roughly the same. For more information about how this works, see Pathfinding.HierarchicalGraph.