You might consider using a drop-down menu (AKA a pop-up menu).
This gives a quick indication of the size of the result-set, as well as allowing the user to jump to the first, last, and any interim page, with reasonable ease.

This is from http://www.edinburghbicycle.com/browse/clothing/mens-clothing
In user testing, I found the most important thing was to have massive next/previous buttons.
Lazy-loading is a better solution - but that's easy to say...