The tale of the li~Nga

Source: here.

The tale of the li~Nga as the phallus of shiva is found in several purANas and is hence not a late concotion. It can be traced back to the bhArgava redaction of the sauta literature. The following purANas state the story:
brahmANDa 1.2.27
kUrma 2.37
skanda 1.1.6, 7.1.187 and other references
vAmana 22.6.65
devIbhAgavata 4.20
shiva 4.12

The critical version of the core tale as can be reconstructed from the above sources goes thus:

The great god rudra, deep in sorrow over he loss of his consort sati at the conflagration in daksha’s yAga wandered into the devadAru vR^iksha vana. The bhArgavas and angiras, with their women and children had made this forest their abode and performed their yAgas and tapasya. The mighty sha~Nkara, wandered naked in this forest with a skull bowl. He performed aTTahAsa by prancing about, yelling and laughing aloud like a madman. Seeing his naked form with erect phallus, the womenfolk of the atharvans were filled with amorous passion and rushed towards him. Seeing their wives thus excited the sages rushed out to discern the cause and saw the form of shiva before them. Infuriated the bhArgavas and the angiras cursed, the deva: “May your li~Nga dettach itself and fall”. Concomitant with the falling of mahAdeva’s li~Nga there were several catastrophic upheavals in the 3 worlds. brahmA alarmed at this went to the lotus-eyed wielder of the drinker of jalandhara’s life. madhusUdana told him the cause for these events and they set out with the other devas to locate the phallus of nIlakaNTha. Unable to locate it, they worshipped rudra, who told them that they would find it and the cataclysms would cease if the worshipped the linga. They fould the li~Nga and brahmA and viShNu picked up the reddish-brown phallus but were unable to install. So they invoked umA to bear it in the form of a vagina. Thus the li~Nga came into being as a symbol of rudra and the gods worhipped it. viShNu initiated the four castes of men in the worship of the linga mUrti and promulgated the shAstras required for it.
divya-lingaM namAmi| shriman mahAdevAya namaH|

It is of interest to note in this context that the veda of the bhR^igus and the angiras has a couple of sUktas devoted to the un-maning of people by surgical methods.