I have something similar that runs on a weekly basis.  I only want to impact the new items on the search.  I used a tag to keep track of what items were already processed.

The search looks for items that match the search criteria that do not have the tag.

Then it processes the required actions on all the of search results, and one of the actions is to add the tag to the item to say it was processed, then it doesn't come up next time.

You could do something similar, adding a tag to each item after it processes.  Then you could just keep running your Workflow until every record is processed.  If you want to avoid having to re-run the Workflow after each failed attempt (every 10,000 actions), the I would recommend setting up your Workflow to limit the number of search results returned, may to something like 500 records.  Then have a condition to determine if the number of results was 0 or more.  If it was zero, you'll just end the Workflow without further action.  But if it is between 1-500, add the subfolder, and then add the tag to the entry, and then start a new instance of the Workflow, which will start the search all over.  The reason it does nothing if there are no results, is so that it has a way to end, since each instance of the Workflow that finds records, will trigger the workflow to load again (you don't want that to continue triggering over and over until your server crashes).  You could even do a reverse workflow to clean up the tags afterwards, for a fresh start in the new year, it would do the search just for the records with the tag, and then remove the tag.