How can I efficiently show the number of total results per channel when retrieving search results?
I would try one of the following solutions:

Using Ajax to display the search results and the filter
Use ajax to display your search results. After loading the search results, you'r using a second Ajax call to get the categories filter. With this solution the visitor see the results quickly and get the filter after. You could try to including caching of the filter to speed up the page. Downside: Depending on requests and amount of content, it needs still a lot of server power.

Writing your own Plugin
Write your own search filter plugin with your logic and optimized SQL to get the filter faster. This solution can be combined with the first one.

Using a external Search Engine
A other solution could be to use a external search engine service like Google Custom Search. Some of them offers filters/logic like you need. Craft CMS Example: On https://straightupcraft.com/craft-plugins/ the search is provided by Algolia (https://www.algolia.com/). On the right side is a simple developer filter, including number of entries.
Take also a look at the Algolia Plugin to easy integrate Algolia in Craft CMS -&gt; https://straightupcraft.com/craft-plugins/search-plus-1