Google quickly gets a set of results from some servers, and then estimates the total.
Say, for example, that their Search cluster has 10000 nodes. And suppose that the query returns 60 results from the first node itself; so it could multiply 60*10,000 and claim there may be 600,000 results. But when it is asked to actually go and fetch the results, for various reasons, it may not get to that figure; most of the nodes may just shrug and say "we got nothin'".
Say, for example, that their Search cluster has 10000 nodes. And suppose that the query returns 60 results from the first node itself; so it could multiply 60*10,000 and claim there may be 600,000 results. But when it is asked to actually go and fetch the results, for various reasons, it may not get to that figure; most of the nodes may just shrug and say "we got nothin'".