How accurate were histories thought to be by medieval historians? What constituted the historical record? Did folk lore and songs carry as much weight as the churches' histories or other written documents?
When you state medieval historians, what you really mean are Catholic monastery monks who would transcribe the old pagan stories, myths, and histories onto paper with an agenda (often with plenty of Christian embellishment).
Many of the natural histories during the Early and Middle Ages were suppressed and repurposed to serve the Church's political interests. The Medieval times begin with the fall of Roman decadence, generations of war and suffering. Accuracy wasn't at the forefront of the Christian monks' minds, as were their beliefs of improving upon a failed society. With the fall of Rome, the great migrations occurred- bringing with it more war, destruction, and famine. An intellectual and social belief vacuum opened up and now there was a market for new ideas that could shape the world. Mysticism and folklore were still very fresh amongst the nomadic tribes, and it was incorporated together as generations passed and Christianity spread throughout Europe by conquerors such as Charlemagne. ("The Vanishing Paradigm of the Fall of Rome")
Most literature during this time would often have a mix of history, myths, and Christian dogma, typically describing a conflict between man and nature ("Beowulf") until we reach the Protestant Reformation and the Renaissance. This doesn't mean that the Church didn't entirely care for history or science for that matter (science is based on historical evidence), but they mostly kept that to themselves till the late middle ages. Monks had to be careful not to show signs of heresy and it was not easy for them to share their work until the invention of the printing press.
Despite the failures of the Crusades, it also brought with them the trade of ideas with Muslum countries, they were far more advanced in terms of the humanities, recorded histories, mathematics, and sciences. This connection helped spark curiosities within Christian scholars and paved the way for the rediscovery of the lost Greco-Roman humanities, philosophies, and histories. This is when a period of seeking historical accuracy would occur. ("The History of the Renaissance World")
Medieval historians were not very accurate. I don't think accuracy and history were linked yet. History was about imparting a message the historian wanted to relate. The best way to interpret their writings is to consider their biases and take them into account. Two biases (institutional and personal) include what organization they belong too ( church, kingdom etc.. ) and their relationship they had with who they were writing about. Authorial Intention in Medieval Historiography
As for folk lore and songs, yes they are part of the historical record as were tapestries; but again you consider the source, consider their bias's because what passed for historians in the ancient times (even Medieval times) were absolutely biased. History as a impartial retelling of events is a relatively modern thing. Last hundred years or so. You don't think George Washington actually threw coins across the Potomac river at Mount Vernon, the river is half a mile wide there.. Nor did he chop down a cherry tree, nor was he known to have never told a lie.