Ever since I was a child reading LOTR, I was under the impression that magic was slowly leaving Middle-earth, and this notion was quite common among fellow fans. I was wondering what Sauron's plan was to deal with this fact after his victory (since he is a magical spirit), but googling it only gave me a result that the "fading" of magic is not mentioned anywhere in canon and is more of a collective notion of parts of Fandom.
Canonically, is magic leaving Middle-earth or not?
Short answer: Magic is leaving Middle-Earth, but it is leaving Middle-Earth because the 'higher' beings have left or are leaving or have been destroyed.
This is a very interesting question, but not one which can be definitively answered by quotes from LotR or The Silmarillion.
The key to the question, I think, is that "magic" is not a thing in Middle-Earth in the sense of being a force or whatever that adepts manipulate. Instead, it is in some mysterious fashion -- Tolkien is far too good a writer to get specific -- a manifestation of a being's self, and the "higher" the being, the greater the "magic" that being can do.
At the Council of Elrond, Gandalf says:
Even if you chose for us an elf-lord, such as Glorfindel, he could not storm the Dark Tower, nor open the road to the Fire by the power that is in him.'
In Lorien, Galadriel says to Sam:
'And you? ' she said, turning to Sam. 'For this is what your folk would call magic. I believe; though I do not understand clearly what they mean; and they seem also to use the same word of the deceits of the Enemy. But this, if you will, is the magic of Galadriel. Did you not say that you wished to see Elf-magic? '
Going right back to the beginning of Middle-Earth, Tolkien again and again shows great feats of what we'd call magic being the result of one-time inspiration from the deepest parts of a person's being. E.g., Yavanna's creation of the Two Trees, Feanor's creation of the Silmarils and the Teleri's building of the white ships.
Yavanna spoke before the Valar, saying "The Light of the Trees has passed away, and lives now only in the Silmarils of Feanor. Foresighted was he! Even for those who are mightiest under Iluvatar there is some work that they may accomplish once, and once only. The Light of the Trees I brought into being, and within Eä I can do so never again.
For the Bad Guys, in ''Morgoth's Ring'' Tolkien talks about how Morgoth, to gain dominion over creation, took the larger part of his own being and melded it with creation. He gained power -- magic -- but at the expense of part of himself.
Likewise Sauron, about whose Ring Gandalf says:
He only needs the One; for he made that Ring himself, it is his, and he let a great part of his own former power pass into it, so that he could rule all the others. If he recovers it, then he will command them all again, wherever they be, even the Three, and all that has been wrought with them will be laid bare, and he will be stronger than ever.
and
If it is destroyed, then he will fall; and his fall will be so low that none can foresee his arising ever again. For he will lose the best part of the strength that was native to him in his beginning, and all that was made or begun with that power will crumble, and he will be maimed for ever, becoming a mere spirit of malice that gnaws itself in the shadows, but cannot again grow or take shape.
So, magic --power over creation -- comes from within and is proportional to how much of your being you are willing to commit. It is not a mechanical thing but more something of supernal inspiration. The key difference between good and bad magic is intention, and bad magic -- such as magic used to dominate others -- can be used up and destroyed to the permanent diminution of the essential being of the user. Beings such as Yavanna who used her power entirely for good seem not to have been as affected by it.
By the ending of LotR, the beings who have the most power: the Valar, the Maiar and the High Elves have almost entirely left Middle-Earth and, woith them, went most of the magic.
(Note: There are many bits here and there about spells and lower grade wizards and suchlike. But there's not enough information to prove that they fit into this framework -- or that they don't.)
