You’re underestimating the difficulty - actually downloading, parsing and updating the system with billions of pages was a very hard thing in the 1990s.
It's not an algorithmic issue, though, that's a systems issue. GGP was talking about the cyclic link nature which isn't an issue of size, it's an issue of convergence.
Good thing there weren't billions of pages in the 90's.
In 1997, there were only a hundred thousand web pages. Not even millions.
The one billion mark would not be breached until 2016 according to the results of a quick search.