An associated myth is that the victims of the European witch persecutions were actually preservers of a secret Goddess-worshipping tradition in northern Europe. This is a really bizarre notion, since there's no evidence that those accused of witchcraft were even pagans. (See Norman Cohn, Europe's Inner Demons, NY: Basic Books, 1975.) In any event, Celtic and Germanic religion was not exactly women-friendly, so we'd need to suppose at least two layers of secret tradition. Worse, the witch-craze was a phenomenon, not of the introduction of Christianity, but of the the sixteenth and seventeenth centuries, i.e. a millennium or so after the conversions, and (not so coincidentally) smack in the middle of the Christian wars of religion.
As to the claim that nine million people were killed as witches, I'd point out that this is a number comparable to the contemporary populations of entire European countries (the whole of continental Europe --- much of which was untouched by the craze --- numbered no more than 120 million in 1700, and that was a historic high); that no mainstream historian gives an estimate within even an order of magnitude of that number; that I can't find any citation which breaks it down by country and time-period; and (most distastefully of all) that it is one-and-a-half-times six million.