If your collection is truly random access (array, search results, relational sets) then use a form that takes the 'foreign key' as input. Then there's one URL and standard query parameters.
In pretty much all other cases a collection would have data/metadata in the response that far outweighs the links. And given that it's perfectly fine for the links to be completely opaque, there's no reason for them to be very long.
The real problem with pagination is that all but a few brave souls completely fuck up the implementation of it. This is the worst possible way to paginate something, but just about every webapp ever written does it like this:
SELECT * FROM posts ORDER BY date DESC LIMIT x OFFSET n*x
The locations of items on pages change constantly as new items are created and destroyed! You page through the history (usually via links with the worst possible names:
prev &
next), and the items shift around as you move around. It's OK that the page with the most recent items changes as new ones are created, but having the archives be a pushdown stack is just idiotic.
Shit would be less fucked if the pages would count up instead of down -- with the oldest items on page 1 and the newest on page N: http://www.dehora.net/journal/2008/07/20/efficient-api-pagin...
It would be terrific if people used meaningful pagination instead of arbitrary offsets: posts by year/month/week/day/hour/minute/second/etc. is far better than "Page N" -- you don't even need to give me any options, just use older/newer links that point to the level of granularity that would give an appropriate number of results.