UserCountsPlugin.php

<?php
namespace Craft;

class UserCountsPlugin extends BasePlugin
{
	public function getName()
	{
		return Craft::t('User Counts');
	}

	public function getVersion()
	{
		return '0.1.0';
	}

	public function getDeveloper()
	{
		return 'Mike Pepper';
	}

	public function getDeveloperUrl()
	{
		return 'https://www.twitter.com/mdcpepper';
	}

	public function modifyUserSources(&$sources, $context)
	{
		if ($context == 'index')
		{
			foreach ($sources as &$source)
			{
				if (array_key_exists('heading', $source))
				{
					continue;
				}

				$criteria = array_merge(
					(isset($source['criteria']) ? $source['criteria'] : array()),
					array('limit' => null, 'status' => null)
				);

				$total = craft()->elements->getCriteria(ElementType::User, $criteria)->total();

				$source['label'] .= " ({$total})";
			}
		}
	}
}

Updated for Craft 3...

use craft\elements\User;
use craft\events\RegisterElementSourcesEvent;
use yii\base\Event;

Event::on(
    User::class,
    User::EVENT_REGISTER_SOURCES,
    static function(RegisterElementSourcesEvent $event) {
        if ($event->context === 'index') {
            foreach ($event->sources as $i => &$source) {

                // If heading, skip
                if (array_key_exists('heading', $source)) {
                    continue;
                }

                // If somehow criteria is missing, skip
                if (!array_key_exists('criteria', $source)) {
                    continue;
                }
                
                // Get all matches, regardless of status
                $source['criteria']['status'] = null;

                // Get total based on criteria
                $query = User::find();
                Craft::configure($query, $source['criteria']);
                $total = $query->count();

                // Append total to label
                $source['label'] .= " ({$total})";
            }
        }
    }
);