You're exactly right: it's not free speach. It's freedom of opinion. The Grundgesetz stipulates that you can walk up to Angela Merkel and tell her that her policies screwed up the nation without her being able to put you in prison. But denying that the Holocaust happened is an outright lie and has nothing to do with speaking truth to power.
It might be a lie in the objective sense, but it is certainly possible to imagine Holocaust-deniers whose belief that the Jews screwed up the country is just as genuine as the person who thinks that of Merkel. There is a long side discussion about how many such people there are, of course. But that gets into pragmatics.
Oppositely, I think our collective epistemic certainty that the earth is round is even higher than our (already very certain belief) that the Holocaust happened. Yet few people think that the government should prevent people from saying this.
Personally, I believe freedom of speech is a false goal. I'm 100% OK with governments restricting speech because it helps the population flourish. But it's a false frame to just make the question a matter of "truth".
Personally, I'm mostly in favor of them, but I think there can be a strong case that Holocaust denial laws are bad for society.
