Там, где вы добавляете свой пункт меню, в title своего пункта добавьте такое значение:
$menu_title .= ' <span class="update-count">' . $count . '</span>';
Ну а сам $count уже отдельно считайте. Я бы сделал это отдельной функцией с кешированием, и просто возвращал из нее циферку. Тогда код будет выглядеть:
$menu_title .= ' <span class="update-count">' . get_my_count() . '</span>';
где get_my_count() и есть моя функция подсчета того, что надо считать (о чем в самой задаче ни слова).