Thanks Brenden, I ended up using this a Repeater with Custom Query as instructed on this article.
You were right, it does count all the pages in the categories.
Now, I just need to figure out how to filter the results based on certain path. For example, I only want to display category items count for all the pages under Podcasts which has tons of pages under it. Any ideas? Filter the custom query by NodeAliasPath?