Here are two attempts to distinguish among several common synonyms related to this question. From Merriam-Webster's Collegiate Dictionary, Eleventh Edition (2003), addressing the words decay, decompose, rot, putrefy, and spoil, all of which "mean to undergo destructive dissolution":
DECAY implies a slow change from a state of soundness or perfection ("a decaying mansion"). DECOMPOSE stresses a breaking down by chemical change and when applied to organic matter a corruption ("the strong odor of decomposing vegetation"). ROT is a close synonym of DECOMPOSE and often connotes foulness ("fruit was left to rot in the warehouse"). PUTREFY implies the rotting of animal matter and offensiveness to sight and smell ("corpses putrefying on the battlefield"). SPOIL applies chiefly to the decomposition of foods (""keep the ham from spoiling).
And from S. I. Hayakawa, Choose the Right Word: A Modern Guide to Synonyms (1968), addressing the words rot, decay, decompose, molder, putrefy, and spoil, all of which "refer to the breakdown of dead organic tissues by natural bacterial processes":
Rot is the least formal and most forceful of these words, suggesting an advanced point in this process of breakdown; the tissues at this point might or might not be foul-smelling but they would in any case be almost unrecognizable, as compared to their former state: [examples omitted]. Spoil, by contrast, refers to an earlier point in the process of organic breakdown; it is especially applied to foods that have turned "bad" or begun to turn: [examples omitted].
Decay is a more matter-of-fact word than rot, and applies to the whole process of breakdown, but particularly to the end point of total destruction: [examples omitted]. Decompose is a more formal substitute for decay, but is almost clinical in its reference to a point in the process between spoil and rot at which point tissues may be distended and ruptured by a build-up of gases: [examples omitted].
Putrefy refers to the same point of the process as decompose, stressing particularly the presence of foul or poisonous gases and noxious odors: [examples omitted]. Molder might now be thought too precious or euphemistic a substitute for decay. It means to decay gradually and turn into dust: [examples omitted].
Merriam-Webster and Hayakawa seem to agree that decay is the broadest term, since it takes the affected organic object from a state of fitness to one of dissolution. But in other respects, Merriam-Webster focuses on the categories of objects that the various synonyms particularly apply to, while Hayakawa focuses on what he considers the stage of disintegration associated with each synonym.
The odd term out is molder, which Merriam-Webster ignores, and which Hayakawa deems potentially "too precious or euphemistic"—perhaps because (in 1968) the most familiar instance of molder to American English speakers was probably in the folk lyric "John Brown's body lies a-moldering in the grave [but his truth is marching on]." But to me, the process of gradual decay from wholeness to dust seems an especially appropriate way to describe the gradual disintegration of paper, so I endorse FumbleFingers's suggestion.
