CREATE PROCEDURE paging (@rec_per_page int, @page int) AS

set nocount on
select identity(int, 1,1) as id_tmp, myid into #tmp_paging from mytable
select * from #tmp_paging as tmp
inner join mytable as t on tmp.id=t.myid
where tmp.id_tmp BETWEEN (@rec_per_page * @page) AND (@rec_per_page * (@page+1) - 1)
drop table #tmp_paging
GO

Примечания
- myid является первичным ключом для mytable
- если поле myid в таблице mytable также имеет свойство IDENTITY, то необходимо использовать запрос select identity(int, 1,1) as id_tmp, cast(myid as int) as myid into #tmp_paging from mytable для того, чтобы "обмануть" сервер.
- на время выполнения запроса select ... into #tmp_paging ... будет блокироваться база tempdb. Если время блокировки критично, то сначала придется создать таблицу #tmp_paging, а потом уже добавлять в нее записи. Это усложняет код (относительно), но в этом случае будет блокироваться только таблица #tmp_paging.
- можно сделать таблицу #tmp_paging и глобальной (##tmp_paging), возможно, что усложнение кода повысит производительность всего проекта (тут только придется решать вопрос актуальности данных, так что сложный вопрос)