As Ryan pointed out the real problem is with the query dataset not being utilized for subsequent page calls. The cost is in preparing the dataset, not in grabbing a few rows from it.

Does Offset/Fetch notify SQL to optimize that aspect of pagination?