De techniek row_number() zou snel moeten zijn. Ik heb goede resultaten gezien voor 100.000 rijen.
Gebruik je row_number() vergelijkbaar met het volgende:
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
...en heb je een dekkende index voor de column_list en/of een index op de 'OrderByColumnName' kolom?