I think you should probably use wp_list_categories(), which even has parameters for a count, like e.g. show_count and pad_counts. Additionally it supports custom walkers via the walker parameter, but the walker would be based on Walker_Category – source -, which gives you every additional styling option you want.
