Please find below sample code to check how to retrieve more than 5K Records in MS CRM using C# code :
Problem
Statement : Query
Expression can’t fetch more than 5k Records in Ms CRM 
Create a Paging Programmatically
and Execute data present in first page. Then proceed with other pages until
execution completes for all Number of Records in Production. 
C# Code to achieve Solution  using Query Expression : 
 
string countryLocale = "%" + countryId + "%";
                QueryExpression query = new QueryExpression("customerproductwarranty");
                
                // Or
retrieve All Columns
                query.ColumnSet = new ColumnSet(true);
                ConditionExpression condition1
= new ConditionExpression();
                condition1.AttributeName = "locale";
                condition1.Operator =
ConditionOperator.Like;
                condition1.Values.Add(countryLocale);
                FilterExpression filter1 = new FilterExpression();
               
filter1.Conditions.Add(condition1);
               
query.Criteria.AddFilter(filter1);
 
                query.PageInfo = new PagingInfo();
     
          query.PageInfo.Count =
1000;
                query.PageInfo.PageNumber = 1;
               
query.PageInfo.ReturnTotalRecordCount = true;
                EntityCollection myContacts =
service.RetrieveMultiple(query);
 
                Console.WriteLine("First set of Records retrieved are :" + myContacts.Entities.Count);
                objErrorLog.WriteErrorLog("First set of Records retrieved are :"+myContacts.Entities.Count);
                var queryResult = service.RetrieveMultiple(query);
    
           if (queryResult.Entities.Count > 0)
                {
                    count =
customerWarrantyDateFormatFix(queryResult , i , service);
                    i += count;
                }
               while (myContacts.MoreRecords)
                {
                    query.PageInfo.PageNumber
+= 1;
                    query.PageInfo.PagingCookie
= myContacts.PagingCookie;
                    myContacts =
service.RetrieveMultiple(query);
                    Console.WriteLine("More Records retrieved are : " + myContacts.Entities.Count);
                    objErrorLog.WriteErrorLog("More Records retrieved are :" + myContacts.Entities.Count);
                    //Add to the collection
                    var queryResult1 =
service.RetrieveMultiple(query);
                    if (queryResult1.Entities.Count >
0)
                    {                
                       count =
customerWarrantyDateFormatFix(queryResult1 ,i, service);
                        i = count;
                    }
                                    }
             Place your functionalities inside
method : customerWarrantyDateFormatFix so that Operations like Update / Get can
be performed. 
  
C# code to achieve using Fetch XML : 
string countryLocale = "%" + countryId + "%";
// int recordCreatedBeforeDays = createdBeforeDays;
// Define the fetch attributes.
// Set the number of records per page to retrieve.
int fetchCount = 5000;
// Initialize the page number.
int pageNumber = 1;
// Initialize the number of records.
int recordCount = 0;
// Specify the current paging cookie. For retrieving the first page, 
// pagingCookie should be null.
string pagingCookie = null;
            try
            {
String fetchRecordsfromCRMforNonAutoWarrantyCountries = @"<fetch version='1.0' output-format='xml-platform' mapping='logical' distinct='false'>
                      <entity name='contact'>
                       <all-attributes />
                        <order attribute='fullname' descending='false' />
                        <filter type='and'>
                          <condition attribute='locale' operator='like' value='" + countryLocale + @"' />
                          <condition attribute = 'emailaddress1' operator= 'not-null'  /> 
                          <condition attribute='modifiedon' value='" + lastXDays + @"' operator='last-x-days'/>
                        </filter>
                      </entity>
                    </fetch>";
                while (true)
                {
                    string xml = string.Empty;
                         xml = CreateXml(fetchRecordsfromCRMforNonAutoWarrantyCountries, pagingCookie, pageNumber, fetchCount);
 
                    // Excute the fetch query and get the xml result.
                    RetrieveMultipleRequest fetchRequest1 = new RetrieveMultipleRequest
                    {
                        Query = new FetchExpression(xml)
                    };
EntityCollection returnCollection = ((RetrieveMultipleResponse)service.Execute(fetchRequest1)).EntityCollection;
                    
}
                    // Check for morerecords, if it returns 1.
                    if (returnCollection.MoreRecords)
                    {
                        Console.WriteLine("\n****************\nPage number {0}\n****************", pageNumber);
                        objErrorLog.WriteErrorLog("\n****************\nPage number {0}\n****************", pageNumber.ToString());
                        // Increment the page number to retrieve the next page.
                        pageNumber++;
                        //refresh the connection
                        service = (IOrganizationService) conn.OrganizationWebProxyClient ?? (IOrganizationService) conn.OrganizationServiceProxy;
objErrorLog.WriteErrorLog("connection refreshed");
                        Console.WriteLine("Connection refreshed");
                        // Set the paging cookie to the paging cookie returned from current results.                            
                        pagingCookie = returnCollection.PagingCookie;
                    }
                    else
                    {
                        // If no more records in the result nodes, exit the loop.
                        break;
                    }
    }
            catch (Exception e)
            {
                Console.WriteLine(" No Records fetched for given Query  ");
                objErrorLog.WriteErrorLog(" No Records fetched with Exception  " + e);
            }