Other people might have objections to this concept, but, this seems reasonable to me:
HEAD /your/api HTTP/1.1
HTTP/1.1 200 OK
Date: Fri, 23 Oct 2009 00:58:17 GMT
Content-Type: application/xml; charset=UTF-8
Content-Length: 89
X-Result-Count: 100000000
And then:
GET /your/api HTTP/1.1
HTTP/1.1 200 OK
Date: Fri, 23 Oct 2009 00:58:17 GMT
Content-Type: application/xml; charset=UTF-8
Content-Length: 89
X-Result-Count: 100000000
<?xml version="1.0" encoding="UTF-8"?>
<results>
100000000 results go here.
</results>
Note: A HEAD request is used here to obtain the count without having to pull the full data set. HEAD requests retrieve only the HTTP headers, not the body of the response.
This would be the most RESTful way I can think of indicating how many results you're gonna get back before you send it over the wire. The main trick is just coming up with the best header name for it. X-Result-Count is decent, but if you can find prior art and reuse their header name choice, that would be even better (as long as they didn't name it something really dumb). That said, I don't expect you'll have much luck, so you should probably stick with X-Result-Count.
Also, I think you may have misunderstood what "REST" actually entails. There's no reason you can't give a representation by range. For example:
GET /your/api?page=1&perpage=10 HTTP/1.1
HTTP/1.1 200 OK
Date: Fri, 23 Oct 2009 00:58:17 GMT
Content-Type: application/xml; charset=UTF-8
Content-Length: 101
X-Result-Count: 10
<?xml version="1.0" encoding="UTF-8"?>
<results>
First 10 results of 100000000 go here.
</results>
However, to be RESTful, you need to be able to tell the client about the representation identified by /your/api?range=0-9 or /your/api?page=1&perpage=10 without using out-of-band information. For example, if your /your/api page would return too many results, do a temporary redirect to /your/api?page=1&perpage=10, and include hyperlinks to /your/api?page=2&perpage=10. Note that a hyperlink in this context could be something simple like:
<?xml version="1.0" encoding="UTF-8"?>
<results>
<result>
This is a result.
</result>
<result>
This is also a result.
</result>
<link rel="next" href="/your/api?page=3&perpage=2" />
<link rel="prev" href="/your/api?page=1&perpage=2" />
</results>
Now the information to navigate the results of your API calls is in-band and actually RESTful.
Essentially, REST is plain-old-HTTP with caching done right and usually sensible URIs thrown in for good measure. It's also "hypertext as the engine of application state" (i.e. resources should link to other resources). It is not a protocol, it's an architectural style. Anyone who tells you differently had better be named Roy Fielding.
Addenda:
If you want to indicate the total count versus the page count, you can define the header like so:
X-Result-Count: 0-9/100000000
Or adjust as necessary.
