CRM 2011 has added a count to all list views but this count is limited to 5000 records; if you have more than 5000 records, you will get "Records 1-x of 5000+".
If you have an On Premise installation, you can change this limit but beware of the following remarks:
First, this is done for a good reason as counting all the records in a view for a given user is NOT a simple table count but has to use the view filter and the CRM Security model; so is a rather complex query which will induce records lock.
If a lot of records are being locked, SQL Server will (depending on configuration) escalade the rows lock to a full table lock for the duration of the select.
In a small system with a low data load, this has no much impact (it's just a count afterall) but if you have thousands of users; you will definitely feel the pain.
Second, changing system parameters directy in the database is totally unsupported; so beware of what you are doing as you may render your system unoperable (you have been warned).
All this said, fire Microsoft SQL Server Management Studio, connect to your CRM database instance and run the following script :