La técnica row_number() debería ser rápida. He visto buenos resultados para 100.000 filas.
¿Está utilizando row_number() similar a lo siguiente:
SELECT column_list
FROM
(SELECT column_list
ROW_NUMBER() OVER(ORDER BY OrderByColumnName) as RowNum
FROM MyTable m
) as DerivedTableName
WHERE RowNum BETWEEN @startRowIndex AND (@startRowIndex + @maximumRows) - 1
... y tiene un índice de cobertura para column_list y/o un índice en la columna 'OrderByColumnName'?
