SQL Server – Get Would-Be Row Count Without Running Twice

So I have a stored proc that utilizes a paging function to only return a subset of the query along with the actual total row count.
In other words, it takes parameters for the start and end rows to slice, and through an Out parameter, should return the total rows that are capable of being selected, along with returning the selected data.

So far, the only effective solution I've found is to run the query twice, once with the row-limiting settings in place and once without, just to execute the count(*) function to get that total.

The current windowing function uses a CTE as the main part of the query, but I'm fiddling with temp tables, and everything I try to simplify the query results in the script becoming slower.

Is this really the best approach?

--Tables


CREATE TABLE [dbo].[tbl_DCCDR_OpenRequests](
    [DCCDRID] [varchar](50) NOT NULL,
    [ACCTNO] [decimal](8, 0) NOT NULL,
    [AltAcctNo] [varchar](30) NULL,
    [APPLCT] [varchar](35) NULL,
) ON [PRIMARY]

CREATE TABLE [dbo].[tbl_HIST](
    [FileOrderID] [int] IDENTITY(1,1) NOT NULL,
    [RefreshRunDT] [int] NOT NULL,
    [CFOFileOrderDT] [int] NULL,
    [ACCTNO] [int] NOT NULL,
    [AltAcctNo] [varchar](30) NOT NULL,
    [APPLCT] [varchar](35) NULL,
    [CFOOrderReasonCode] [varchar](3) NOT NULL,
    [DCCDRID] [varchar](50) NOT NULL,
    [CFOReqstType] [smallint] NOT NULL,
    [ActiveException] [bit] NOT NULL,
    [FileOrderCloseDT] [int] NULL,
    [FileDestructionDT] [int] NULL,
) ON [PRIMARY]



CREATE TABLE [dbo].[tbl_FileOrderEscalation](
    [EscalationID] [int] NOT NULL IDENTITY (1, 1),
    [FileOrderID] [int] NOT NULL,
    [EscalationOpenedBy] [varchar](50) NOT NULL,
    [EscalationOpenedDate] [datetime] NOT NULL,
    [EscalationClosedBy] [varchar](50) NULL,
    [EscalationClosedDate] [datetime] NULL,
    [Note] [varchar](255) NULL,
 ) ON [PRIMARY]




-- =============================================
-- Create basic stored procedure template
-- =============================================

-- Drop stored procedure if it already exists
IF EXISTS (
  SELECT * 
    FROM INFORMATION_SCHEMA.ROUTINES 
   WHERE SPECIFIC_SCHEMA = N'dbo'
     AND SPECIFIC_NAME = N'CFOSearch' 
)
   DROP PROCEDURE dbo.CFOSearch


CREATE PROCEDURE dbo.CFOSearch
    @Search varchar(50) = '', 
    @includeCompleted bit = 1,
    @StartAt bigint = 0,
    @ReturnRows bigint = 0,
    @TotalRowsResult bigint = 0 out
AS
Declare @Result bigint
    if @ReturnRows > 0 BEGIN set rowcount @ReturnRows END

    declare @SearchIn varchar(52) 
    SELECT @SearchIn = '%' + @Search + '%'
    ;with result as (
    select *
    -- Add Row Number so we can have paging
    , ROW_NUMBER() OVER (ORDER BY FileOrderID) as row_number
    from (
    select 
    FileOrderID
    --Display Escalation status (0 = not escalated, 1=escalated)
    , Escalated
    --Display the matchType
    , case 
    when ISNUMERIC(@Search) = 1 and 
        (
           ACCTNO like @Search
        or FileOrderID like @Search
        ) then 'Account Number or File Order ID'
    when AltAcctNo like @Search then 'Alternate Account Number'
    when APPLCT like @SearchIn then 'Applicant Name'
    else 'Unknown' end as [MatchType]
    , RefreshRunDT
    , CFOFileOrderDT
    , ACCTNO
    , AltAcctNo
    --, *
    from tbl_HIST
    outer apply (select COUNT(*) Escalated from [tbl_FileOrderEscalation] e where FileOrderID = e.FileOrderID and EscalationClosedDate is null) e
    where
        case when @includeCompleted = 1 then 0
            else  FileOrderCloseDT
        end = 0
    and (
        ISNUMERIC(@Search) = 1 and 
        (
           ACCTNO like @Search
        or FileOrderID like @Search
        )
        or AltAcctNo like @Search
        or APPLCT like @SearchIn

    )
    --Union in all the requests that are submitted, but dont yet have an order
    union all
    select -1, 0, 'Submitted CDR request (No order)',o.ACCTNO, o.AltAcctNo, APPLCT

    from [tbl_OpenRequests] o
    left join tbl_HIST h on o.DCCDRID = h.DCCDRID
    where
    h.FileOrderID is null and
    ISNUMERIC(@Search) = 1 and 
        (
           o.ACCTNO like @Search
        )
    ) o)
    select 
      FileOrderID
    , Escalated
    , [MatchType]
    , ACCTNO
    , AltAcctNo
    , APPLCT
    from result 
    where row_number > @StartAt
    order by row_number

    --Get the rowcount and return it as an output parameter
    select @TotalRowsResult = COUNT(*)
    from (
    select ACCTNO
    from tbl_HIST
    where
        case when @includeCompleted = 1 then 0
            else  FileOrderCloseDT
        end = 0
    and (
        ISNUMERIC(@Search) = 1 and 
        (
           ACCTNO like @Search
        or FileOrderID like @Search
        )
        or AltAcctNo like @Search
        or APPLCT like @SearchIn

    )
    --Union in all the requests that are submitted, but dont yet have an order
    union all
    select o.ACCTNO
    from [tbl_OpenRequests] o
    left join tbl_HIST h on o.DCCDRID = h.DCCDRID
    where
    h.FileOrderID is null and
    ISNUMERIC(@Search) = 1 and 
        (
           o.ACCTNO like @Search
        )
    ) a
    --Also return it as a normal output
    return @TotalRowsResult

GO

-- =============================================
-- Example to execute the stored procedure
-- =============================================

declare @Result int
execute dbo.Search '0', 1, 40,20,@Result out

select @Result