Performance of a categories list with post count
I don't think you'll be able to avoid the database queries, but you'll definitely want to use cacheing here, and set a high cache time if possible.

Wrap your code in {% cache %} tags like below: 

{% cache globally for 1 month %}
{% nav category in craft.categories.group('...') %}
   {% set entryCount = craft.entries.relatedTo(category).total() %}
   {{ category.title}} ({{ entryCount }})
{% endnav %}
{% endcache %}


If this navigation appears on every page, use the "globally" tag.