A técnica row_number() deve ser rápida. Tenho visto bons resultados para 100.000 linhas.
Você está usando row_number() semelhante ao seguinte:
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
...e você tem um índice de cobertura para a column_list e/ou um índice na coluna 'OrderByColumnName'?