Paradise Lost is a real-life 17th century English epic poem by John Milton. It tells about the Judeo-Christian story of the Fall of Man, the temptation of Adam and Eve by the fallen angel Satan and their expulsion from the Garden of Eden. Its significance to history (and to the game), however, comes from its infamously harsh critical stance on the self-righteousness of Christianity; in Paradise Lost, Satan is a tragic hero fighting for the ideals of individualism and rationalism.
A curious contradiction can be observed when talking to Tulip: she explains that Underworld is based on this book which she says is about a man making a trip through the Underworld. The book she is actually referring to and the one Underworld is based on is actually Dante Alighieri's Inferno, the first canticle of his Divine Comedy.