The only thing that should be interpolated is rendering. Pathfinding is part of AI, which, like physics, is part of the "business rules" side of the game, and therefore should be running at a constant rate, which has to be tuned to not eat too much CPU time on slower computers and defines the minimum specs for running the game.
If you don't care if everyone's opponents are equally smart, you can always glance at the clock each time through the loop/level of recursion and cut off the pathfinding if it's taking too long. If you're planning all of the routes through a map (at least on a macro scale - hierarchical, highway-like pathfinding saves a lot of time if you can stand the occasional quirks of its behavior) at runtime, you might be able to set up a system that steals a few cycles whenever there's time left over while the previous area is being played and then only blocks if it still isn't done when needed. But at that point, why not compute those paths really ahead of time (at map build) and then load them in as part of a map file?
If you don't care if everyone's opponents are equally smart, you can always glance at the clock each time through the loop/level of recursion and cut off the pathfinding if it's taking too long. If you're planning all of the routes through a map (at least on a macro scale - hierarchical, highway-like pathfinding saves a lot of time if you can stand the occasional quirks of its behavior) at runtime, you might be able to set up a system that steals a few cycles whenever there's time left over while the previous area is being played and then only blocks if it still isn't done when needed. But at that point, why not compute those paths really ahead of time (at map build) and then load them in as part of a map file?