Well, not magical maybe but certainly supernatural. I recently read a source, a letter from a French monk, in Rouen, writing to a colleague at another monastery during the eighth century. In it he discusses at length word that he has gotten from a missionary friend working to evangelise the Swedes about the "dog people" that live in the far north. The interesting thing is that he does not seem to take them as supernatural, but takes their existence as objective fact. He then goes into a long discussion about whether they have souls like humans or not and eventually concludes that they do, in part since they domesticate animals and practice agriculture and must therefore have been elevated above the animals to or near to the levels of human, despite their appearance. To support his argument about dog people soulfulness he pulls out some books from the monastery library discussing similar topics, it seems as if the status of non humans was in fact a long running discussion on which there had been some scholarship done. This might support a thesis that even the highly educated, which this man clearly was since he was literate, could quote the bible and in my opinion had read some of the classics, believed in what we now would call the supernatural or the fantastical. However, we could argue about whether this man though that the dog people were in fact supernatural or just another creation of God's kingdom.

The question conflates two separate concepts: Folk tales and folk belief.

To first address the former, folk tales are a narrative form of oral prose and there is no requirement of credulity on the part of the audience for them to function as narratives. In other words, neither the storyteller nor the audience needs to believe the story. That said, defining folktales as essentially fictional is not entirely correct either, as Carl Lindahl et al. examines in Medieval Folklore:

Some scholars use the term folktale very generally and literally, to designate any tale shared orally in folk communities. More commonly, however, folklorists use the term for works of oral fiction told to entertain or educate, thus separating them from legends, tales in which belief is a major factor and which are usually told as true, even if their truth is often debated.

If we choose to define folktales not simply as narratives but particularly as fictional narratives, we must establish that such tales were considered fictional by the medieval narrators and their listeners. We seldom get such precise information.

Consider the plot of one of the most popular tales in European tradition, known and endlessly repeated from ancient Greece to twentieth-century Scotland: a monster terrorizes a kingdom, demanding an annual tribute of virgins, chosen by lot to fulfil his lust and hunger. One year the lot falls to the king's daughter, and the desperate king offers her in marriage to anyone who will slay the monster. A hero appears, kills the monster, and then cuts out its tongue. An imposter, intent of marrying the princess and inheriting the kingdom, finds the dead monster, cuts off its head and presents it to the king, and is about to marry the princess when the hero suddenly reappears to produce the tongue and prove that he is the rightful husband of the princess.

This plot, known to folklorists as "The Dragon-Slayer" (AT 300), appears, fully or partially, in Greek myth (the story of Perseus), medieval saints' lives (including the story of St. George and the dragon) and romances (for example, the Tristan of Gottfried von Strassburg), as well as postmedieval märchen--for example, as the tale of the "Two Brothers" in the Grimms' Kinder- und Hausmärchen (Children's and Household Tales), better known as the Grimms' Fairy Tales. Many medieval and postmedieval narrators have presented the tale of St. George as a true story, but few if any listeners believe the Grimms' version of the same plot to be a factual account. Thus, plot outline and content alone simply cannot establish whether a surviving medieval tale is a work of fiction.^^1

The distinction between fictional and non-fictional narratives is important to understand, as applying either designation may alter understanding of the material. Take the narrative of the famed Sun Tzu as recounted by Sima Qian, who relates how the warrior-philosopher trained the concubines of King Helü of Wu, by executing the king's two favourite concubines when the rest failed to follow his orders:

The king, watching from his stand, was aghast to see that his favourites were about to be executed and hastily sent messengers with orders, saying, 'I can see you are an able general. But without those two concubines my food would lose all flavour. I beg you to spare them.'

Sun Wu replied, 'I have been appointed commander, and a general in the field is not bound by orders from his sovereign.' So he had the two leaders killed as an example, and made the next two officers.

This time, when he sounded the drums, the women turned left or right, advanced and retreated, and knelt or stood up exactly as they were told, not daring to utter a sound.

Then Sun Wu went a message to the king, saying, 'The troops are in fighting trim, ready for inspection. Your Majesty can do what you please with them - they will go through fire or water.'^^2

The story is unmistakably a version of the popular international folktale The Taming of the Shrew (ATU 901), which has been collected in several hundred versions spread over dozens of languages. In this instance however, the narrative is written as a historical account.^^3 So while folktales may often take the form of fictional narratives, special caution must be exercised to avoid characterizing as fiction what was intended as truth.

---

As regards the latter part of your question, the answer is more philosophical because of the broad generality of the question itself. The Irish folklorist Caoimhín Ó Danachair rhetorically presents much the same question in Irish Customs and Beliefs:

A problem which sooner or later confronts every ethnologist is that of the degree of credence in the many curious details of what he terms folk belief. Do people really believe in the Good People?^^4

Yet, if there is attestation for beliefs, why doubt them? There is certainly no lack of such attestation within my own area of study, and I have no cause to suspect Ireland is unique in this regard. Medieval insular texts suggest a vivid belief in the quasi-natural, one that is kindred to the equivalently wondrous oral tradition. Such belief is a fundamental thread of the cultural fabric, as Seán Ó Súilleabháin stresses in his A Handbook of Irish Folklore:

It is difficult to bring within such a small compass even in a schematic way the various facets of [folk belief] whose ramifications are co-extensive with human thought and activity, and to give at the same time suitable examples to guide the collector in his enquires. Many of the items dealt with or referred to in the other chapters come also, of their nature, within the scope of the present pivotal one in which all traditional customs and beliefs are focussed.^^5

His conclusion is plain: You cannot divorce belief from tradition or practice and hope to have a meaningful understanding of the tatters remaining. Scepticism - while not itself unhealthy, is not so easily disentangled from bias in this case. This sort of 'enlightened' scepticism colours earlier studies of belief which often viewed such 'superstition' as the base of an evolutionary pinnacle that rose from 'primitive magic' upwards to religion and then finally to a peak of modern 'civilized' scholarly thought. As Angela Bourke notes:

Oral cultures were found all over the world until well into the twentieth century, but in the heyday of European colonialism they were overwhelmingly interpreted, in the light of Darwinian ideas, as primitive and childish - charming, perhaps, but certainly incapable of any discriminating engagement with reality.^^6

This is not at all the case. There exists no metric by which one belief might be weighed as more advanced than another, nor for that matter one which evaluates whether they are genuinely held or not. Our modern 'enlightened' culture itself is an inextricable syncretism of beliefs:

The influence of the fairies was apparent in an event which occurred in County Mayo, where they caused the re-routing of a public road. The story of what happened is here taken from a newspapers account in the Daily Mail, 23rd April, 1959. A new road was being built at Toorghlas, Co. Mayo. In the course of construction they came to a fairy palace which would have to be destroyed if the road were to be built as planned. Twenty-five Land Commission labourers went on strike rather than interfere with the domain of the Good People.^^7

Even when given serious cause to doubt whether certain beliefs are authentically held, proving them as spurious is likely futile if not outright impossible. Angela Bourke's The Burning of Bridget Cleary, her investigation into the 1895 incident in which an Irish woman was burned to death by her husband, can serve as a final dramatic punctuation of this point. Michael Cleary had tormented and killed his wife Bridget after she became ill, allegedly under the belief she had been replaced by a Changeling. The event scandalized the nation and his arrest and trial were documented as much in the press as the courts. Whether Cleary truly believed his wife had been replaced by a supernatural imposter lay at the heart of the affair. However the credibility of this belief simply could not be genuinely determined despite his vehement pleas of earnestness. He was eventually convicted in spite of this:

Michael Cleary, the Clonmel Chronicle reported, 'wept bitterly while his lordship was speaking, and when being removed from the dock shouted out that he was innocent'.^^8

Bourke, likely the foremost living authority on the case, herself also struggled and failed to answer the very question you've posited. From this most sensational of episodes we may perhaps conclude the only sincere arbiter of true belief is the believer themselves; if our aim is to understand such beliefs we ought give their opinion strong consideration.

---

^^1 ^(Carl Lindahl, John McNamara, and John Lindow. Medieval Folklore: A Guide to Myths, Legends, Tales, Beliefs, and Customs. Oxford, New York: Oxford University Press, 2002. pp. 342-344.)

^^2 ^(Qian Sima. Shi Ji Xuan: Selections from Records of the Historian. trans. Yang Xianyi and Gladys Yang. Beijing: Wai Wen Chu Ban She, 2001. pp. 145-147.)

^^3 ^(Bairbre Ní Fhloinn. "From Medieval Literature to Missiles. Aspects of ATU 901 in the Twenty-First Century." Fabula 51, no. 3-4 2010. pp. 187-200.)

^^4 ^(Caoimhín Ó Danachair. Irish Customs and Beliefs. Cork, Ireland: Mercier Press, 2004. p. 30.)

^^5 ^(Seán O Súilleabháin. A Handbook of Irish Folklore. Detroit, Michigan:Singing Tree Press, 1963. p. 362.)

^^6 ^(Angela Bourke. The Burning of Bridget Cleary: A True Story. New York: Penguin Books, 2001. p. 24.)

^^7 ^(Reidar Christiansen. “Some Notes on the Fairies and the Fairy Faith”. Béaloideas 39/41, 1971. An Cumann Le Béaloideas Éireann. pp. 95–111.)

^^8 ^(Bourke, p. 189.)

/u/Bealoideas did a great job answering this question. A few things can be added or emphasized:

The medieval period includes several centuries, many different cultures, and a wide spectrum of possibilities when it came to education and wealth, so generalizations are difficult. In addition, every culture can have skeptics, so always keep that in mind.

Pre-modern European peasantry believed in a wide variety of supernatural creatures, so we can project backwards and assume that this was generally true in earlier periods, and primary sources bear this out - and again /u/Bealoideas provides excellent sources.

And as /u/Bealoideas indicates, folktales (which are often called fairy tales) were typically told for entertainment not to be believed (and they were adult entertainment, usually not for children although their modern literary counterparts were adapted for children). But even when told as fiction, these folktales necessarily integrated a lot of fantastic creatures and supernatural beings that had to be believable for the story to work. In addition, whether a story type was told to be believed or not depended on context: when the folktale ATU 300 (the dragon slayer) was told in reference to someone like Saint George, it was told to be believed (and can be referred to as a historical or religious legend), and people would generally believe it; but when the same story was told about a hero in the context of a folktale, the story was not meant to be believed. But in either case, the existence of a dragon - even if it was in a former time - was not necessarily doubted.

At the same time, people told legends - stories generally told to be believed. Among these were "Testimonial" or "Migratory" legends, which testified to the existence of supernatural beings and creatures. These stories could be extremely persuasive just as their modern counterparts, the urban legends, are. People told these stories, and although one would necessarily encounter skeptics, people in pre-modern settings generally took these stories on faith and believed them. There is every reason to conclude that the same held true for medieval societies in general.

I'm not sure what you mean by "mystical" in this question. It seems somewhat begging the question. It took a long time to be absolutely sure that the world really did contain no actual physical dragons or mermaids or unicorns. It took a long time for the world to be explored and news about what there is where is still reaching people today. (I read the other day of someone alive now, who believes the earth is flat - or says he does). You might be skeptical of what you were told (the "vegetable lamb" of Tartary, anyone?) but it would be hard to be sure. It's there in the books, and you are not going to go and look for it yourself, are you? And even if you did, how are you to know that the centuars are not just over that hill you didn't have time to climb?

St Augustine of Hippo refers in City of God to a debate as to whether fauns (as in Mr Tumnus, not as in Bambi) and "sylvans" had souls or not, and if so, whether they were saved or damned. He comments that the first thing to establish was whether fauns and sylvans actually exist, and after that we could discuss the rest.

Which suggests a pleasantly skeptical view of legends, but there is no sense that he regards them as "mystical" - rather as real, mortal beings which either exist in creation, or don't.