Sql-server – Stored procedure optimization

In my application I am using the below stored procedure, but it is taking a long time to execute. Both tables contain millions of records. Please guide me to optimize this procedure. I have searched a lot but not found any better way.

 CREATE PROCEDURE [dbo].[sp_SearchReportAdminPanel]
 @UserName nvarchar(max),
 @FromDate datetime,            
 @ToDate datetime,            
 @RecepientNumber nvarchar(max),            
 @Status nvarchar(max),            
 @SenderId nvarchar(max),  
 @PanelMasterId BIGINT = 1,
 @PageIndex INT = 1,        
 @PageSize INT = 10,        
 @RecordCount INT OUTPUT
 WITH RECOMPILE        
AS                      
BEGIN          
SET NOCOUNT ON;
DECLARE @SkipPageRank INT = (@PageIndex - 1) * @PageSize ;

SELECT temp.*,um.usr_Mobile_No as UserName INTO  #Results FROM 
( 
 SELECT XML_Id, Temp_Id, RIGHT(Mobile_number,10) as Recepient, Message_Text as Text,    
        Coalesce(Message_Status, 'Sent') as Status, CreatedDate,DeliveryDate,User_Id     
 FROM  Table1 xmd WITH (NOLOCK)            
 WHERE (xmd.CreatedDate between @FromDate AND @ToDate) and 
    (RIGHT(xmd.Mobile_number,10) = @RecepientNumber OR @RecepientNumber = '') and           
    (Coalesce(xmd.Message_Status, 'Sent') = @Status OR @Status = '') and            
    (xmd.Sender_Id = @SenderId OR @SenderId = '')   
 UNION ALL
 SELECT XML_Id, Temp_Id, RIGHT(Mobile_number,10) as Recepient, Message_Text as Text,    
        Coalesce(Message_Status, 'Sent') as Status, CreatedDate,DeliveryDate,User_Id   
 FROM  Table2 xmd WITH (NOLOCK)            
 WHERE (xmd.CreatedDate between @FromDate AND @ToDate) and 
    (RIGHT(xmd.Mobile_number,10) = @RecepientNumber OR @RecepientNumber = '')   and         
    (Coalesce(xmd.Message_Status, 'Sent') = @Status OR @Status = '') and            
    (xmd.Sender_Id = @SenderId OR @SenderId = '')
) temp INNER JOIN Table3 um WITH (NOLOCK) on temp.User_Id = um.usr_Id
WHERE
    (um.usr_Mobile_No = @UserName OR @UserName = '') and
    (um.PanelMasterId=@PanelMasterId)

   SELECT @RecordCount = COUNT(*) FROM #Results        

   select * from #Results
   ORDER BY XML_Id DESC    
   OFFSET @SkipPageRank ROWS
   FETCH NEXT @PageSize ROWS ONLY

    DROP TABLE #Results        
END