How would one describe the tension between paganism and christianity in medieval literature?
The writings of the time were religious and secular. Paganism would have reflected beliefs in the deities and traditions of pagan religions prior to the arrival of Christianity.
Christianity did its best to gain a foothold in Europe, and in doing so, celebrated many Christian holidays when pagan holidays were celebrated, thereby blurring the lines between the two.
In terms of literature, most of what was written during this time was religious in nature. The majority of those able to read and write were part of the church. English drama of the time was religious, in the form of miracle (humorous) and morality ("fire and brimstone") plays. The church was also responsible for recording the history that had been passed down verbally (oral tradition) and events of importance of the present day.
Secular literature was made up of medieval romances which included chivalry and love, but also magic, which would not have overly pleased the church. (Chivalry was encouraged by the Church to improve the behavior of knights, making each a "knight of Christ" or miles Christi.) There was also literature based upon politics, and battles and heroes (Beowulf was this kind of literature, Germanic in origin, though probably passed down in the oral tradition long before it was ultimately recorded in writing.)
In the first five hundred years of this period, Christianity established itself throughout Europe, developed a complex institutionalized religion capable of governing society at all levels, ministering to the sick, and dealing with judicial disputes; the Church hammered out compromises with secular rulers...
As Christianity permeated all levels of society in spreading throughout Europe, it had to contend with the "old ways," pagan beliefs that were rooted deeply in the values of the common people.
In literature of the time, as in every other facet of society, Christianity walked a fine line to discourage a fostering of pagan beliefs, while using those same beliefs to incorporate the precepts of the Roman Catholic Church into the people's mainstream perceptions and ideas. I believe it is safe to say that the church gently discouraged the old belief system in pagan literature and encouraged the growth of Christianity, at least at this time, by including some reference to Christianity in most literature of the time, even archaic pagan tales. Old literature that had been strictly pagan to that point became acceptable as Christian allusions were added to stories and poetry, often by monks as they recorded the pieces.
Tension between the two was quietly addressed, and wisely so if the church had hopes of winning people to a new way of seeing the world and their place in that world, ruled by the hand of Christianity.