It's not exactly what you are looking for, but the marking dialog will tell you. For example, create a group with the exact same marking criteria as you are using for your search. After the marking, it will tell you how many individuals were marked. You don't even have to complete the making of your group. Just cancel out after the marking is done.
I've been trying to think of an easier way to get into the marking dialog. For example, color coding will also do it. Again, cancel out before the color coding is complete. Or as another approach to play with, actually do make your group and put your group into People View. At that point, you can just go down the list and you don't have to search again because you already did the searching when you made the group.
Maybe somebody else can think of an easier way to get into the marking dialog. I do agree that when you set out on such a task, it can be very useful to know how big the task is going to be.