In CRM2011 it is now possible to get the Total count of records returned by a query using Fetch XML.
Using Query expression:
You can set the ReturnTotalRecordCount property to True.
Using FetchXml:
You can set the same property as shown below.
This can be helpful to show Record 1 of
Hope this helps!