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")