In interviews, Dawkins usually responds that (1) Stalin didn't do all those bad things because he was an atheist, and (2) his ideology was rather based on "blind faith" and has more in common with religion than with a rationalist-naturalist atheism. I am afraid this kind of response is not effective enough. Point (1) is lost on most of the sound-bite audience, which is generally unable to tell causation, correlation, and coincidence from each other. Besides, it is an obviously falsifiable hypothesis, so why should it convince a rational opponent without evidence (which can't be packed in a sound bite)? And it is not sexy enough to convince irrational opponents. Point (2) is very good standing by itself, but it redefines the frame of the debate that Dawkins had set up. I have always preferred to group pervasive ideologies with religion, but Dawkins, who entered the debate over religion through the "evolution vs. creationism" gate, had not had the need to do that, which may make him ill-equipped to argue this particular point.
From comments on Pharyngula, here is an excellent answer to the SWAA fallacy that fits in a sound bite:
there is a world of difference between believing that there is no god and believing that there is one, and you're it!
I will adopt this word-for-word, with thanks to David Livesay. It is very effectively framed and presented, while not compromising on the truth. It contains the two most critical points for debunking SWAA:
There is a god in every totalitarian ideology. When an idea becomes more important than people, when it is considered worth sacrificing the lives of many people and the welfare of many others to that idea, then that idea is indistinguishable from God. Dogmatic Communism is a religion in every practical sense of the word.
Stalin substituted himself for God. This should not be taken as literally as the first point, but it is a metaphor that captures the attitude of every totalitarian dictator quite accurately. It is especially true if the dictator exhibits signs of paranoia, which Stalin certainly did, and to which dictators in general are prone. We'll never know what went on in Stalin's head, but it is possible that he viewed God not as a non-entity, but rather as his rival, as another alpha-male to fight for the leadership of the pack. In any case, the practical consequence was that the Christian Trinity was merely replaced by the Trinity of Stalin's personality, the state ("Motherland"), and the Communist Party. A similar argument can be made that most other totalitarian dictators considered themselves divine in some sense.
I think the real debate should not be between atheism and religion, but between the rationalist/naturalist/skeptical world view and the dogmatic/idealistic/faith-based one. But that's a topic for another post...