MySQL COUNT resultados de UNION ALL declaración

Si te entendí correctamente, esto debería hacerlo:

SELECT page_id, count(*)
FROM tags
WHERE tag IN ('New Zealand', 'Trekking')
GROUP BY page_id
HAVING count(*) > 1

No necesita usar una UNIÓN si selecciona de la misma tabla.