El group by lo tienes bien, pero te falta la condicion del join (te hace la multiplicación cartesiana de los registros, por eso te salen tantos).
Código:
SELECT COUNT(men_usuid) as counter, men_usuid, usu_nick
FROM men_mensajes, usu_usuarios
WHERE men_mensajes.men_usuid = usu_usuarios.usu_id
GROUP BY men_usuid, usu_nick
