Credo di aver risolto con questa:

UPDATE utenti SET sesso = 'M'
WHERE EXISTS (
SELECT 1
FROM uomini
WHERE utenti.nickname LIKE CONCAT('%', uomini.nome, '%'));


l'ho testata su una tabella "utenti" ridotta a qualche centinaio di record e ha funzionato. Ora sta girando sulla tabella vera e propria, che però contiene molti più record e quindi impegnerà il pc per credo diverse ore...