This answer focuses on the rationales behind the Holocaust denial law in Germany (Section 130 (3) of the German criminal code). I assume that the reasoning in other jurisdictions was similar. But I would like to invite other users to post answers which focus on other countries.
The German Holocaust denial law was made in 1994 after the Bundesverfasungsgericht Bundesverfasungsgericht (Germansupreme constitutional court) ruled in BVerfGE 90, 241 (German source) that banning Holocaust denial is constitutional. The reasoning was that the fact that the Holocaust happened is an undeniable historical truth, and any attempt to claim the opposite can only serve the purpose to insult Holocaust victims and justify violence against those minorities who were the targets of the Holocaust. They judged that protecting the dignity and safety of these minorities is more important than protecting the speech of the Holocaust deniers.
The above-mentioned ruling also goes to great lengths to refute the "freedom of speech" counter-argument. The usual German translation of "freedom of speech" is "Meinungsfreiheit" which literally means "freedom of opinion". The constitutional court reasoned that whether or not the Holocaust happened is a fact and not an opinion. According to the constitutional court, the German definition of freedom of opinion only covers statements which cannot be proved or disproved. Therefore, denying the Holocaust is not speech which is protected by article 5 of the German basic law.