Cossacks (released in 2002) is an RTS game where you can build huge (few thousands men per player) armies on a really big maps. Imagine Age of Empires 2 for few players on Ludikris map with no lag, with 8000 units on the map (or even bigger map with even more units!). What is interesting is the fact, that if you send this huge army to the other corner of the map ... the game does not stall. Units just start moving towards their target position. There are obstacles on the way, like hills, buildings, walls etc, which are avoided by units.
There is, however, a problem with pathfinding - sometimes units just go back and forth around hills, so that might indicate, that whole path length is divided into smaller parts and units' gets confused. But still, that's massive amount of computation to be done for a few-thousand-men army, really impressive.
Do you have any idea how such smooth (in terms of performance) pathfinding was/could be achieved?