Ran into this problem and searched high and low for a solution but never found another post detailing the solution.
The issue is that, according to the documentation for GetListItem, located here:
Paging should be done like this:
The GetListItems method supports server-side paging. The XML data returned by this method includes a ListItemCollectionPositionNext attribute inside the rs:Data element that contains the information to support paging. This string contains data for the fields in the sort and for other items needed for paging. You should consider this string internal and not to be modified; modifying it can produce unexpected results. The following example shows the form of this return value when paging is supported.
To get the next page of data, the queryOption parameter is used, as shown in the following example.
The trick is to build the XML string with that information blank like this:
<Paging ListItemCollectionPositionNext=”” />
Then load it into the XmlElement using the InnerXML, as before.
optionsQuery.InnerXml = queryOptions;
The go directly to the attributes innertext and set the value:
optionsQuery.ChildNodes.Attributes["ListItemCollectionPositionNext"].InnerText = "Paged=TRUE&p_ID=100&View=