Haven't done this, but the way I would do it is to make a query to search (f.e. using REST) and ask to return tags as refiners (create a refinable managed property, if it's not there yet). Refiners have a RefinementCount property, which gives an approximate number of hits. Creating a link to search for each refinement result (tag) shouldn't be difficult either. This way you only do one search query to get everything that you need, which is really efficient.
An example REST API query, which will return all items in search index:
Once you create this refinable managed property RefinableTags you should get all possible used tags and their count in the resultset PrimaryQueryResult/RefinementResults/Refiners, for example:
You can use RefinementCount for the count, RefinementName to display to user and RefinementToken to create a URL to a search page which refines by this tag (i.e. shows all results with that tag). You will need to URL encode this, but for clarity's sake I'll post this unencoded:
Edit: just now noticed that you might want to open a search page with the taxonomy written in the search box. In that case it's even easier, just construct the search query in k parameter:
or for more accurate results: