Clear-SPListItems.ps1 simulates SPWeb.ProcessBatchData() using CSOM to batch ListItemCollection item deletes. Feedback welcome! To see what is going on under the covers, run Fiddler and watch the traffic for the requests.

Clear-SPListItems.ps1

# =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=
#       Script: Clear-SPListItems.ps1
#
#       Author: Pete Skelly
#		Twitter: ThreeWillLabs
#               http://www.threewill.com
#
#  Description: Purge list in Sharepoint Online - Office 365 using CSOM by 
#               batching CSOM calls to simulate SPWeb.ProcessBatchData().
#
#		WARNING: This script will DELETE all list items!!  Script provided
#               as is with no warranty.  Your mileage will vary.  Use this script
#               on a production list AT YOUR OWN RISK. 	    	
#
# =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=

param(
  [string]
  $siteUrl,
  
  [string]
  $userId,

  [string]
  $listName,

  [int]
  $batchSize
  
) 

$ErrorActionPreference  = 'Stop'

# ---------------------------------------------------------
# Load SharePoint 2013 CSOM  libraries.
Add-Type -Path "c:\Program Files\Common Files\microsoft shared\Web Server Extensions\15\ISAPI\Microsoft.SharePoint.Client.dll"
Add-Type -Path "c:\Program Files\Common Files\microsoft shared\Web Server Extensions\15\ISAPI\Microsoft.SharePoint.Client.Runtime.dll"
 


$password = Read-Host -Prompt "Enter password for $userId" -AsSecureString

$ctx = New-Object Microsoft.SharePoint.Client.ClientContext($siteUrl)
$credentials = New-Object Microsoft.SharePoint.Client.SharePointOnlineCredentials($userId, $password)
$ctx.Credentials = $credentials
 
$list = $ctx.get_web().get_lists().getByTitle($listName);
$ctx.Load($list)
$ctx.ExecuteQuery()
$itemCount = $list.ItemCount;
$listType =  $list.BaseType;
Write-Host "List contains $itemCount items.  List type of $listType"
	
#See http://msdn.microsoft.com/en-us/library/microsoft.sharepoint.client.camlquery(v=office.15).aspx for details on these calls
$itemsDeleted = 0;
$listID = $list.ID.ToString()

#create objects to be used to delete in batches
$camlQuery = New-Object Microsoft.SharePoint.Client.CamlQuery
#Create a query to get items by id's in batches
$camlQuery.ViewXml = "<View><ViewFields><FieldRef Name='Id'/></ViewFields><RowLimit>" + $batchSize + "</RowLimit></View>";		
$camlQuery.ListItemCollectionPosition = $null	#set initial query position (starts as null)
$items = $list.GetItems($camlQuery)		#execute the query
$ctx.Load($items);				#load the items 
$ctx.ExecuteQuery();				#execute the entire operation set
$retCount = $items.Count 
if ($retCount  -gt 0)
{
	do{
		Write-Verbose -Message "Query returned $itemCount items..."

		Write-Verbose -Message "Building batch..." 
		$items | 
			% {
				$delItem = $list.GetItemById($_.ID);
				$delItem.DeleteObject();
			}
		Write-Verbose -Message "Executing batch..." 
		$ctx.ExecuteQuery();
		
		$itemsDeleted = $itemsDeleted + $batchSize

	} while ($itemsDeleted -le $itemCount)	
}
else
{
	Write-Verbose -Message "No list items returned."
}

This doesn't seem to actually work. The problem is that you retrieve one batch of items (line 64), loop around to delete those but then don't retrieve a new batch. So the second run will process the exact same ID's which already have been deleted. At least that's what it does on my side.

I got the same result as @jsiegmund above, but was able to resolve by replacing line 79 with the following lines (which I copied from before the do loop

$items = $list.GetItems($camlQuery)		#execute the query
$clientContext.Load($items);			#load the items
$clientContext.ExecuteQuery();			#execute the entire operation set