If the result set is "all users", you probably don't want to pull tens or hundreds of millions of records just to count them up if you're showing 100 per page.
I think that something like a query for hundreds of millions of records that also required pagination for the exact number of records returned is anomalous and not something that their application would do.