The verse quoted from Padma Purana's Vishnu Sahasranama most probably refers to the battle between Narayana and Rudra described in this chapter of the Shanti Parva of the Mahabharata. The Sanskrit verses for the same can be referred here.
It is the 343rd chapter of Shanti Parva as per KMG's source recension, and the 352nd Chapter as per the Kumbhakonam recension of the Mahabharata. (The chapter number differences are more due to the difference in splitting up of chapters rather than additional chapters between recensions.)
In this chapter, while explaining some of his names to Arjuna, Lord Krsna talks about those names wherein he identifies himself with Lord Shiva (in the sense that Hari and Hara are the same entity who have taken two different forms). These names include Ishana, Munjakesha, Khandaparashu and others.
In this regard, Krsna mentions of a battle between Narayana, the son of Dharmadeva and twin brother of Nara, and Rudra, Lord Shiva in his fierce form as the destroyer of Daksha Yaaga.
In the due course of the destruction of Daksha's sacrifice, Rudra releases a Shula (lance) to destroy the beings who participated in the sacrifice. Having burnt the intended, the Shula proceeds towards Badarikashrama, where Nara and Narayana are performing penance.
tachChUlaM bhasmasAtkR^itvA dakShayaj~naM savistaram.
AvayoH sahasA.agachChadvadaryAshramamantikAt.
vegena mahatA pArtha patannArAyaNorasi.. 12-352-44
"That Shula, after destroying Daksha's Yajna, came towards us (Nara and Narayana), and with great force slammed on Narayana's chest."
tattasyatejasA.a.aviShTAH keshA nArAyaNasya ha.
babhUvurmu~njavarNAstu tato.ahaM mu~njakeshavAn.. 12-352-45
tachcha shUlaM vinirdhUtaM huMkAreNa mahAtmanA.
jagAma shaMkarakaraM nArAyaNasamAhatam.. 12-352-46
"Affected by the energy of the Shula, the hair of Narayana turned the colour of Hay (Munja), by which I came to be called Munjakesha. Narayana then let out a great Humkara by which the Shula was rendered effectless and returned to the hands of Shankara."
Following this a battle occurs between Narayana and Rudra wherein Narayana grabbed hold of Rudra's throat, causing it to change into a dark blue hue, following which he came to be called Shitikantha.
To prevent further destruction, Brahma requests Rudra to cease the fight and make peace with Narayana, who was after all engaged in penance and not fighting battles. Rudra does as Brahma requests him to, and Narayana becomes pleased with Lord Shiva and says how he and Shiva are the same reality in two different forms for the benefit of the world.
brahmaNA tvevamuktastu rudraH krodhAgnimutsR^ijan.
prasAdayAmAsa tato devaM nArAyaNaM prabhum.
sharaNaM cha jagAmAdyaM vareNyaM varadaM harim.. 12-352-64
"Upon hearing the words of Brahma, Rudra discarded his anger and pleased Narayana, the excellent one, the bestower of boons, the reliever of distress, and sought his refuge."
tato.atha varado devo jitakrodho jitendriyaH.
prItimAnabhavattatra rudreNa saha saMgataH.. 12-352-65
R^iShibhirbrahmaNA chaiva vibudhaishcha supUjitaH.
uvAcha devamIshAnamIshaH sa jagato hariH.. 12-352-66
yastvAM vetti sa mAM vetti yastvAmanu sa mAmanu.
nAvayorantaraM kiMchinmA te.abhUdvuddhiranyathA.. 12-352-67
"Then the Lord Varada (bestower of boons), conquerer of anger and senses became pleased with Rudra and had a parlay. Being worshipped by Brahma, Devas and the rishis, Narayana, the Lord of the worlds, spoke to Rudra — 'Whoever understands you understands me. Your followers are mine. There is no difference between you and me, let there not be second thoughts on this."
He then bestows upon Shiva the appellation "Shreekantha" since Rudra's Kantha was held by Narayana's auspicious hands. He further names the mark which the Shula made on his chest as Shrivatsa.
adyaprabhR^iti shrIvatsaH shUlA~Nko me bhavatvayam.
mama pANya~NkitashchApi shrIkaNThastvaM bhaviShyasi.. 12-352-68
"From today let your Shula's mark on my chest be called Shrivatsa, and my hand's mark on your throat give you the name Shreekantha."
Thus, rendering Lord Shiva's Trishula effectless, Narayana, the son of Dharmadeva, accompanied in Badarikashrama by Nara, Krsna and Hari, bestowed boon of a new appellation, and unparalleled friendship (Atulam Sakhyam, 12-352-69) upon Shreekantha.
User @Saurav Dey pointed out that no destruction happens to Rudra's Shula, as also the fact that the Shula is not mentioned as three-pronged.
I would like to mention that the verb Vidhvams, while commonly meaning destruction, or reducing to pieces, also means, "to injure or hurt" according to Monier Williams' Sanskrit dictionary.
Also, when referring to Lord Shiva's weapon, he is invariably called Shulapani, Shuli and so on, and it is understood that the Shula of Shiva is a three-pronged lance. Hence the mention of only Shula in the Shanti Parva as opposed to Trishula in the Sahasranama verse can be equated as a synonymous reference.