Boa pergunta!
"Quantos é demais?" - isso, é claro, depende do tamanho dos dados e dos requisitos de desempenho. Eu, pessoalmente, me sinto desconfortável quando pulo mais de 500-1000 registros.
A resposta real depende de suas necessidades. Aqui está o que os sites modernos fazem (ou, pelo menos, alguns deles).
Primeiro, a barra de navegação se parece com isso:
1 2 3 ... 457
Eles obtêm o número da página final da contagem total de registros e do tamanho da página. Vamos pular para a página 3. Isso envolverá alguns saltos do primeiro registro. Quando os resultados chegam, você sabe o id do primeiro registro na página 3.
1 2 3 4 5 ... 457
Vamos pular um pouco mais e ir para a página 5.
1 ... 3 4 5 6 7 ... 457
Você entendeu a ideia. Em cada ponto você vê a primeira, última e atual páginas, e também duas páginas para frente e para trás a partir da página atual.
Consultas
var current_id; // id of first record on current page.
// go to page current+N
db.collection.find({_id: {$gte: current_id}}).
skip(N * page_size).
limit(page_size).
sort({_id: 1});
// go to page current-N
// note that due to the nature of skipping back,
// this query will get you records in reverse order
// (last records on the page being first in the resultset)
// You should reverse them in the app.
db.collection.find({_id: {$lt: current_id}}).
skip((N-1)*page_size).
limit(page_size).
sort({_id: -1});
