The annual fees to use the algorithm is probably not substantial and a quirk of the agreement, and the substantial part of the licensing agreement is the 1 million or so shares that they received.

The share grant must have been fairly early on the history of the company (or else Google won't be able to use PageRank, which was fundamental to Google Search), probably pre-Series A. Google itself wasn't worth that much back then, so the 1M shares was probably bigger slice of a much smaller pie that eventually got diluted through later funding rounds.