Multimap звучит как правильный выбор, однако, вы могли бы сделать
public static <K, V> int count(Map<K, ? extends Collection<V>> map) {
int count = 0;
for (Collection<V> coll : map.values()) count += coll.size();
return count;
}
Кстати: вы можете рассчитывать, чтобы вернуть длинный;)