Ah. But was Nobunaga referred to as the "demon king"?

There is one single surviving source that refers to Nobunaga as "Demon King of the Sixth Heaven", that of Jesuit Missionary Luis Frois in his letter to fellow missionary Francisco Cabral.

No other known Japanese primary source, whether in the Sengoku or in the Edo period, referred to Nobunaga as "Demon King". This means either Nobunaga was never referred to as "Demon King" or it was not widespread enough to survive. As Frois' one letter is also the only western source to pair Nobunaga with the title (well, it was the only source to do so, western or otherwise), we can be very certain that a very small number of Europeans would have heard Nobunaga with this label.

Let's take a look at the letter itself. It is dated 1573, April 20th. In it (the letter's quite long, the link is only a tiny section), Frois tells Cabral about the war that has been going on in the Kinai between Nobunaga and the lords that surrounded him. Unsurprisingly, Frois put great emphasis on Christian lords, the war's effect on Christians, and missionary activities. The linked section talks about who Takeda Shingen is, describing Shingen as a good general and devote Buddhist who had attacked Tōtomi and Mikawa (land of Nobunaga's ally Tokugawa Ieyasu) and was marching on Owari and Mino, wishing to rebuilt the temple of Enryakuji destroyed by Nobunaga a year and a half prior. Frois, perhaps a bit jarring to modern readers not used to the politics and views of the time, wrote the above descriptions as if they were bad things. He instead praised Nobunaga for destroying the false idols to free the Japanese of superstitions. Frois tells Cabral that

...when this new enemy of the Christians [Shingen] comes to Kyōto, and rebuilds Mount Hiei, it would be damaging to us, so we need to prepare, and all the Christians in Kyōto are very worried, but with God's grace and protection we would easily prevail against the wrath of the devil. Something interesting happened before Shingen invaded Tōtomi and Mikawa, he sent Nobunaga a letter, in it to arrogantly boast his name, in the letter he called himself as such: Tendaino-Zasushamon-Shingen. It means the highest clan of the Tendai religion and teacher Shingen. To this, Nobunaga answered Doiroku-Tennomauo-Nobunaga. It means the enemy of Buddhist sects demon king Nobunaga. As Deva against the Buddha, hindering him from spreading the religion, Nobunaga has to this day hindered the honor and worship of idols, so we should rely on the mercy of God, that He may return us to the glory of old, and as the just answer of our Lord Deus, believe the accursed superstitions of these sects should be punished...

So how likely is it that this letter Frois speaks of was actually real? Immediately suspicious is that no specific date is given, not even month or year, and the content is not mentioned. All that mentioned is how Shingen addressed himself, and how Nobunaga addressed himself in the reply. Yet it just so happens that this fits perfectly into the point that Frois was making to Cabral: that Nobunaga, even though he didn't believe in God, was doing God's work and sweeping away Buddhism. It all seems very neat. Perhaps a little bit too neat. Of course it might just be because Frois was writing probably about six months after this letter, and simply forgot what he didn't find important. However, the lack of date and content combined with the fact that we have surviving sources of Nobunaga's prayer dedication to temples and his stated reason (excuse) of burning Enryakuji, not that he didn't believe in Buddhism but that the monks were corrupt and not following the religion properly, and it's quite a bit suspicious that perhaps Frois was trying to see in Nobunaga something that Nobunaga wasn't in reality. We also need to consider Shingen's plan relied on catching Nobunaga unawares before he could block the mountain passes, and Nobunaga likewise was busy fighting many enemies already and much preferred to keep Shingen on friendly terms. Would either of them risk antagonizing the other before war even broke out? These all make the existence of the letter Frois speaks of a bit questionable.

Whether or not the letter existed, or contained what Frois say it did though, might not be that important. In any case, it is not very likely that Frois himself would have been present when Nobunaga received a letter from Shingen. The story in all likelihood traveled to Frois via word of mouth, and he interpreted what he was told. This would fit with the lack of the letter's date, content, and Frois saying it was just "something interesting". It can also be seen fairly easily as Frois misinterprets the titles he said Shingen and Nobunaga gave themselves. Shingen's "Tendaizasu Shamon (Śramaṇa in Sanskrit)" does not mean head of the Tendai religion but "Disciple/Apostle of the Head of Tendai religion". Which makes sense as no (other) surviving source says Shingen ever laid claim to head the Tendai religion, but at that time the actual head of Tendai, Prince Kakujo, was seeking refuge with Shingen. Likewise, the "Dairokuten Maou", the "Demon King of the Sixth Heaven", is not a demon out to destroy Buddhism, but to tempt and test the faith of Buddhists. If the letter was actually real it's not unlikely that both Shingen and Nobunaga's self-addresses were less hostile than Frois assumed. But we would never know because Frois doesn't tell us the content of the letter.

What likely happened then is that Shingen probably did send Nobunaga one, or many, letter sometime after the summer of 1572. At the time and in the following months Nobunaga, bloody conqueror and the burner of Enryakuji and Shingen, devout Buddhist who had taken in the head monk of Enryakuji, went to war with each other. Regardless of whether or not they addressed themselves as Frois said they did, and if they did whether those titles meant what Frois said they meant, the political climate was ripe for the story of the demon vs the devout to spread in Kyōto. Frois heard the story, and interpreted it based on his own world view as a Jesuit missionary. But given that in a month Shingen would be dead, the story, likely never all that widespread to begin with as it wasn't recorded in any aristocratic diaries or Japanese letters, died out.