Above question is about two situations:
Standard, simple menu with 1-2 levels of depth,
Catalog on commerce site, with number of products, next to every item (taxonomy term) of menu.
I can imagine, that counting all nodes related to every taxonomy term every time when site is accessed would kill the server (if there is like hundreds of products), but views have some cache option, don't they? Can they cache their output and make menus views driven reasonable?