This is a well known and very difficult to solve problem, especially when it comes to large volumes of data. Even not touching SharePoint, you might have noticed that many systems (Google is an obvious example) return only approximate number of filtered elements.
Basically the only thing you can do is to perform the same query but exclude permissions and all fields except ID from the results. So in terms of SQL it will be something like this:
SELECT id FROM list WHERE (filter)
If you have more than 5 000 items in the list (or other value which exceed "Throttling Limit" setting value which you can find in web application settings), you will have to put all the fields which participate in the filter to index (see "Indexed columns" link on the "List Settings" page), and you will have to abandon filtering by Lookup-like fields (these are fields of the following types: Lookup, Managed Metadata, People and Group, Workflow Status).
Also it is advisable to limit even this query by some big number, say, 100 thousand items or something like this, so it will be:
SELECT TOP 100000 id FROM list WHERE (filter)
So, how it will look applied to SPQuery?
var query = new SPQuery()
// please make sure FirstName and FullName fields are added to index!!
Query = "<OrderBy><FieldRef Name='FullName' /></OrderBy><Where><Contains><FieldRef Name='FirstName' /><Value Type='Text'>e</Value></Contains></Where>",
ViewFields = "ID",
ViewFieldsOnly = true,
IncludePermissions = false,
RowLimit = 100000
Please, keep in mind that it will perform slow if you have large amount of items or if you have heavy (in terms of SQL) filter.