Sure, but why should they? They are serving a huge number of users simultaneously, there’s no point in doing work to collect data that the user doesn’t need right away. Remember, Gmail doesn’t know how many pages you’re going to look through. 99.9% of the time nobody looks beyond the first page. It is vastly more efficient to fulfill the request and stop, rather than continuing to search in the background for information that probably will not be requested.
No, they search an index of the web. And they do the same pagination shenanigans on public search as they do in Gmail. Try searching for some weird phrase like chartreuse hippopotamus. Google thinks there are three pages of results, but by the time you get to the second page it turns out there are only two.