row_number() 手法は迅速なはずです。 100,000 行で良い結果が得られました。
次のような row_number() を使用していますか?
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
...そして、column_list のカバリング インデックスおよび/または「OrderByColumnName」列のインデックスはありますか?