The question has a fundamental problem, which is an artificial separation of "science" and "magic". Pre-Enlightenment, this separation simply did not exist. You'll recall that Newton spent much of his life trying to make alchemy work, and numerous other things which we today would consider "magic". Indeed it was the work of Newton, Hooke and all the numerous other "natural philosophers" which first defined the division between science and magic.

Productions of Macbeth typically have the witches as some kind of supernatural special effects, and modern audiences see them as such. For Shakespeare's audience though, this was as realistic as The Wire is for us. Most of us have never met a drug dealer or lived in those areas of Baltimore, but we know it exists and we've probably seen pictures. Shakespeare's audience knew witches existed, and most of them had probably seen a witch arrested, tried and executed.

In this context, separating "science fiction" and "magical fiction" becomes basically impossible. The Tempest could easily be considered science fiction, for example, because Prospero's magic is merely something that's a bit further ahead than the alchemists of the day could manage. Of course Shakespeare wasn't medieval, but he shows the limits of knowledge that still existed several hundred years earlier.

To demonstrate this further, consider the Bible as a science fiction novel. A man is born by parthogenesis, is visited by aliens whilst a baby, is supernaturally intelligent as a child, replicates enough food for thousands of people, has a universal translator with direct stimulation of ears so that everyone hears in their own language, controls the density of matter to make water become solid, heals people, regenerates after a mortal injury, then finally teleports away from his friends after a last goodbye. Separating science, magic and religion simply isn't possible with a pre-Enlightenment view of the world.

The question has a fundamental problem, which is an artificial separation of "science", "magic" and "religious miracle". Pre-Enlightenment, this separation simply did not exist. You'll recall that Newton spent much of his life trying to make alchemy work, and numerous other things which we today would consider "magic". Indeed it was the work of Newton, Hooke and all the numerous other "natural philosophers" which first defined the division between science and magic, and first started the Catholic church's problem with identifying miracles when cause, effect and evidence are better understood.

Productions of Macbeth typically have the witches as some kind of supernatural special effects, and modern audiences see them as such. For Shakespeare's audience though, this was as realistic as The Wire is for us. Most of us have never met a drug dealer or lived in those areas of Baltimore, but we know it exists and we've probably seen pictures. Shakespeare's audience knew witches existed, and most of them had probably seen a witch arrested, tried and executed.

In this context, separating "science fiction" and "magical fiction" becomes basically impossible. The Tempest could easily be considered science fiction, for example, because Prospero's magic is merely something that's a bit further ahead than the alchemists of the day could manage. Of course Shakespeare wasn't medieval, but he shows the limits of knowledge that still existed several hundred years earlier.

To demonstrate this further, consider the story of Jesus as a science fiction novel. A man is born by parthogenesis, is visited by aliens whilst a baby, is supernaturally intelligent as a child, replicates enough food for thousands of people, has a universal translator with direct stimulation of ears so that everyone hears in their own language, controls the density of matter to make water become solid, heals people, regenerates after a mortal injury, then finally teleports away from his friends after a last goodbye. If you want to fictionalise the story of Jesus or saints (and medieval people certainly did!), then whether all this comes from the Holy Spirit, magic or science is completely up for grabs from a modern viewpoint. (Clarification requested by KutuluMike - I'm not saying that the story of Jesus is fiction, just that key elements could be construed that way. In fact this forms the plot of Michael Moorcock's novel Behold the Man.)

My point is that separating science, magic and religion simply isn't possible with a pre-Enlightenment view of the world. Without any recognised differences between those categories when it was written, pre-Enlightenment fiction can't be nailed into any of those categories.