This is similar to what was already suggested but different enough to warrant posting:
Create a table-valued user-defined function that returns the keys for the table. This UDF takes the same parms as your stored proc plus a "skip" count.
Then in your stored proc, do your same select with a TOP 200 and a NOT IN the tables.
Something like this
select top 200 * from table
where IDCol not in dbo.udfQueryParms([same parms as proc], @SkipCount as integer)
This grows increasing inefficient as you page forward.
If you have a table this large, is it stable enough that you could "pre-page" it and add a column that indicated the page number of the row? Then you could just select page by page.
You might need several indexes and page counters to supply the different ways you allow someone to sort.
But I have to think noone will ever page through 800,000 rows 200 at a time. that's 4,000 pages.