Minouche, si vous doutez du caractère correct de « Ils se sont donné tant de mal », voyez cet extrait du Trésor de la langue française informatisé (TLFi) :
« Tant de + subst. Un si grand nombre, une si grande quantité de. Ma santé exige tant de soins!(R. BAZIN, Blé, 1907, p. 167). »

N.B.  La réponse de Joëlle est correcte, malgré le vote négatif. 

Bonne nuit !

Ils se sont donné tant de mal.
Elles se sont donné du mal.

Ils se sont donné raison. Ils se sont donné la main. Ils se sont donné rendez-vous.

Mais : ils se sont donnés entièrement à leur travail.

Il se sont donné tant de mal qu’ils se sont épuisés.
Lisez cet article.

« Tant » est un adverbe qui peut s’appliquer à un verbe, ou à un substantif avec le mot « de ».
— J’ai tant souffert.
— J’ai subi tant de malheurs.
Dans l’écriture moderne, quand le verbe a un COD, c’est au substantif COD qu’on applique l’adverbe. On écrit donc dans votre cas :
— Ils se sont donné tant de mal.
Perd-on une nuance ? On voudrait appliquer l’adverbe au verbe, comme un adverbe d’intensité, et on est obligé de l’appliquer au nom, comme un simple adverbe de quantité ? C’est peut-être pour cette raison qu’on trouve dans la littérature :
— J’ai tant vu de batailles qui ne valaient pas la peine d’être données. (Péguy)
— j’ai tant vu de choses extraordinaires (Voltaire)
— il a tant vu de larmes (Balzac)
— J’ai tant, tant aimé de femmes depuis mon premier renouvellement. (Victor Méric)
— Si les philosophes avaient fait cette observation, ils ne se seraient pas tant donné de peine pour fixer les limites du bien et du mal. (Chateaubriand)
La phrase
— Ils se sont tant donné de mal
est donc valide, mais il faut avoir conscience que c’est une tournure ancienne ou littéraire. Comme par ailleurs « se donner du mal » est une formule très courante, on ressent un petit décalage de style, mais si cela sonne juste pour vous, c’est bon.
Plus banalement, je vous conseille cet usage plus actuel même s’il est plus pauvre :
— Ils se sont donné tant de mal.