Are you saying that your API would require my interface to mimic your pagination, as opposed to being able to retrieve data in such a way that I could paginate as I saw fit?
More importantly, let's say that I am retrieving the default 10 results per request. Let's say there are 15 results. If I request the second "page", what will the next_url value in the response be?
In other words, how can you provide an accurate next_url in your responses if you're not calculating the total number of results? At some point, aren't you providing a next_url that will return 0 results?
While count is expensive, it seems it would be less so than full result set retrieval broken up over several requests?
You'll get some additional usage beyond the 2% who need it now (after all, if it's there people will use it while in its absence it would not be considered at all), but on the whole you should be able to find the threshold at which you'd come out ahead by offering it.