I'm not seeking to supplant any of the answers here, since I think they are all excellent, but to bring a few other points to the discussion:
- The claim that the Holocaust is a fiction is one predicated on the myth that Jews around the world are sufficiently powerful as to perpetrate a hoax of such enormity, and that they are jointly motivated by a shared hatred for the rest of the world.
In other words, that Jews act in concert to deceive "goyim", gain sympathy, make money and rule the planet. Holocaust deniers tend to assert Jewish control over major media outlets and financial conglomerates, and argue that they control (in some sense) the halls of power. They argue that laws against Holocaust denial prove that there is a conspiracy of intimidation, and that such laws are designed to serve the interests of Jews.
Rebuttal: If laws against Holocaust denial service Jews, and if Jews "control" the United States, why are there no laws prohibiting denial in North America?
In actual fact, countries with laws against Holocaust denial also have laws that forbid other types of hate speech, and while those laws might be controversial they are based on the very real fear that denial is a form of endorsement.
- Denying the Holocaust means ignoring or refuting a mountain of evidence too large for any one person to properly explore. I refer to the abundance of material, textual and audiovisual evidence: the vast amount of footage that was recorded (both overtly and covertly), the enormous trove of archived testimony (from survivors, perpetrators and other witnesses), sworn depositions, photographs, documents, reports from contemporary journalists and human rights activists, diaries (of perpetrators as well as victims), etc.
To relegate the entirety of this material to the trashcan is to step beyond the bounds of historical revisionism and entire the realm of denial in the first place. To claim that every piece of testimony was extracted under torture, that every document was doctored, every diary entry forged and every photograph a piece of propaganda is to ascribe either superhuman powers to the small group of people who invented this hoax, or to claim that every Allied country was in league with them in the generation of this myth, as was every Axis power that subsequently subscribed to it. It is to claim, in other words, that the world that Jews seek to rule is the small community of Holocaust deniers, since every other person on the planet is a part of the conspiracy. Furthermore, to assert that Jews are possessed of such powers of machination and that the Nazis didn't want to eradicate them is itself logically bizarre.
Rebuttal: This argument basically boils down to the claim that the work of every historian is a piece of propaganda, but that the work of the Reichsminister of Propaganda somehow wasn't.
In actual fact, the evidence is so exhaustive and the events so well remembered by the local populations of Europe that the number of people who assign the Holocaust in its entirety to the level of a myth tend to be geographically distant from the places it occurred. It's a lot easier to doubt that something happened on the other side of the world than it is to ignore the elderly people in your own community who remember it taking place in their own backyard.
- Perhaps most offensively for many people, denial of the Holocaust amounts to an assertion that survivors have invented their testimony and are pathological liars. To survivors themselves, to their descendants and to those who know them, this is obviously absurd, but to a population of people who only encounter the occasional survivor and only through online or print media, it may not be so radical an idea.
People who hold to this idea will point to discrepancies within survivor testimony, showing how people's stories have changed over the course of time, how they conflict with one another and how they include information now known by historians to be false. Famous examples in this regard include the myths of soap manufacture from flesh, lampshades being made from skin and the feeding of bromide to internees in concentration camps.
Rebuttal: Memory is a fragile tool, for which reason police prioritise hard data (like CC-TV footage) over sworn testimony. Question a person after an awful car accident and see how well they remember the order in which different things happened.
In actual fact, therefore, we expect the testimonies of trauma victims to be erratic and unreliable. Collusion is evidence for a conspiracy; disagreement and contradiction is not.
When Holocaust deniers peddle this material, they tend to favour snappy observations that can be presented in the form of memes - like the observation in the OP's question that concerns the death toll at Auschwitz. Ultimately, arguing with such people (if you are so inspired to do so) is likely to be a fruitless endeavour. The only real cure is education, and there is no longer an excuse for not receiving one. The published material is voluminous, and hundreds of articles are issued every year.
The best books on this subject, and which I would use if I were recommending reading material to a dyed-in-the-wool Holocaust denier, are the following:
Yitzhak Arad, Belzec, Sobibor, Treblinka: The Operation Reinhard
Death Camps. We hear so much about Auschwitz that the name has come
to serve as a metaphor for the Holocaust itself. Arad's study of these
three camps redresses that imbalance. It features extraordinary
testimony from perpetrators and is meticulously researched.
David Cesarani, Final Solution. Just published this year, this book
is highly readable and exhaustive. It contains much material not
previously published, and while it has been panned by various deniers
online, it is patently obvious that they didn't read it but only
cherry-picked its contents.
Raul Hilberg, Sources of Holocaust Research: An Analysis. This book
comprises an exhaustive list of exactly how much and what sort of
information a researcher of the Holocaust may encounter, but serves
also as a pretty exhaustive list of just how much material a denier
would need to ignore.