Adding dynamic markup to menu items
Hope this will help you,


As answered theme_menu_link OR theme_menu_tree wil help you to do this. If you go through the above links you can get an idea to change the html of required menu item. 


On page load: 


for example im using theme_menu_link in template.php refer this code. Node count will be update on every page load, if any changes.
I have updated l() for you requirement. For example I have used a simple function , modify the function as per your requirement.

$output = l($element['#title'] . '&lt;span class="'.strtolower(strip_tags(str_replace(" ", "_", $element['#title']))).'_node_count"&gt;'.get_node_count($parms).'&lt;/span&gt;', $element['#href'], array('html'=&gt;TRUE));

function get_node_count($parms){
    //you code goes here for get node count
    return $node_cnt;
    }



If you don't want on page load, it can also be done using ajax callback, but not preferable to make ajax callback again and again.


If you want to do refer ajax callback, then the only change has to be done in the l(). Add the unique menu id, which is used to show the node count for the corresponding menu id.

$output = l($element['#title'] . '&lt;span id="'.strtolower(strip_tags(str_replace(" ", "_", $element['#title']))).'_node_count"&gt;&lt;/span&gt;', $element['#href'], array('html'=&gt;TRUE));



On sucessfull ajax callback you have to update the node count for each menu.
using
...
success: function(data) {
// Change node count
$('#menu_title__node_count').html(data);
}
You will get the class for each node count, you can style as required. And also you can add a common class for common style, based on your requirement.