Do it in batches with smaller searches. You don't need to go as small as 10, but keeping it in the 100-250 range would provide optimal performance depending on how many activities run in each iteration. 15,000 is a lot of results, but the bigger concern is the for each loop.

When a workflow runs any kind of loop like that, each loop iteration is logged and as you loop that activity data will accumulate and severely impact the workflow's speed as it builds up.

For example, when I first started working with workflow I had a process running on millions of documents. I found that in large batch loops, it would take milliseconds per document in the beginning, but by the end it would start taking minutes per document.

Breaking it into batches will provide optimal speed all the way through, but, it is important not just to break the work into batches but also give each batch a fresh workflow instance.

What I usually do is have a parent workflow that will invoke the "batch" workflow multiple times. So you could have your workflow pull 250 results, then have the parent workflow invoke that in a loop, waiting for each instance to finish, until all of your documents have been addressed.

Basically, the search itself isn't the biggest issue, it's the loop iterations and activity data that accumulates when you iterate the results and take actions on the documents/entries.