>
>What's happening is that I'm applying several filters originally to the data before inserting it into the temp table. After that, I'm running the query to page, and I'm a dozen or so other queries on the data that should return minimal rows.
>
>So, while the temp table may contain millions of records, my stored procedure is returning maybe 10 result sets with maybe 200 combined records.

OK, if you're using SQL 2012...you might want to try this: Here's a simple example that starts after then 40th row and grabs 10 rows using OFFSET and FETCH. Maybe you could try to incorporate these into your code. Again, this accomplishes what CTEs and a filter on ROW_NUMBER used to accomplish in prior versions.

Let me know if these help at all.

declare @rownum int = 40

  SELECT *    FROM Purchasing.Vendor
     ORDER BY Name
         OFFSET (@RowNum) ROWS  
            FETCH NEXT (@RowNum + 10) ROWS ONLY;

If you have a proc that's receiving a page number....

   declare @PageNumber int =11
   declare @RowsPerPage int = 10

   select *  from Purchasing.Vendor Order by Name
            offset (@PageNumber-1) * @RowsPerPage rows
                 fetch next @RowsPerPage rows only