According to Norwegian Folk-Tales, by Reidar T. Christiansen and Pat S. Iversen, Europeans of the late Renaissance shared a belief that such a school existed somewhere. (It was called "The Black School," and its basic text was "The Black Book." Even handling said book was considered dangerous.) Logically, the school had to be some place with a major university -- Salamanca, maybe. Once Lutheranism was declared by royal fiat, Norwegians naturally assumed that the school must be located in the Lutheran capital.
Marlowe's Faustus, of course, was "of Wittenberg doctor," which suggests that it was not only Scandinavians (or Lutherans) who put the school there. But to a 19th-c. translation of Goethe, James Adey Birds adds an introduction which talks about the sources of the poem. The early sources (which are pretty well known to historians; we have seen them elsewhere, and often) certainly do place Faust is critical Reformation cities -- Basel, Wittenberg -- as well as Wuerttemburg and Vienna. But some of them, including one attributed to Melanchthon, claim that his magical training had come at Cracow. (In the Renaissance, Cracow's Jagiellonian University was indeed an international center of learning, particularly distinguished in the natural sciences -- alma mater of Copernicus).
So in all fairness, it may not have been the Lutherans who formed the original Slytherin House. It may have been the Spaniards or the Poles. Or maybe, after the Reformation, we started our own.