It's often said that if a story can be told without its Fantastic elements, then it should go find its real genre. 

I disagree.

Reduced to the essential myth, "Boy meets girl, wizard steals girl, boy kills wizard but girl rejects him because she loved wizard" level, most stories can be airlifted between genres.
 
Think of the Best of Breed fantasy works from times gone by. The Hobbit could be a crime caper, with Bilbo as the humble geek recruited to "stick it to the man". Lord of the Rings, the tale of a pacifist-turned-assassin lugging a rifle to a dictator's heartland in order to get off that one critical shot. Conan would be happy slinging a gun in the Old West, his fists and bullets laying low the minions of cattle barons, railway magnates, and evil industrialists alike.
 
Then come forward in genre history: The coteries of clairvoyants of Robin Hobb's Fitz series echo Bletchley Park, or modern hackers working for the CIA. Fitz himself would exist well in Smiley's world.
 
Magic, then, at the mythic level does not generally make unique stories. (If it did, would we want to read them? I'm not sure. Stories are not intellectual puzzles, or roleplaying game transcripts. They have to resonate with something in the reader.)
 
So in Fantasy literature, what purpose does Magic serve?
 
Most of all, I think, "sense of wonder". Much like tanks and guns in military stories, and gentle hunks in Romance, magic is one of the payloads of the Fantasy genre: read this novel and for a few hours live in the company of wonderworkers and thaumaturges.
 
It has to be more than that. Imagine we wanted to turn a Napoleonic novel into a Fantasy one. Easy! We'll lose the 1800s cannon and swap in mages... And for Brown Bess, we'll have a cool firestick with... BZZZZT!
 
... the story would still feel like a Historical, just with cardboard cut-out Gandolfs gaffer-taped onto the field pieces. It would seem strangely lame compared to the efforts of Tolkein, Hobb and Howard.
 
Imagine Lord of the Rings redone as a thriller set in post colonial Africa, with the Oil Company as the Sauron and Frodo as peace-loving pygmies. With a bit of ingenuity it might make a rather gripping yarn. However, it would be complicated and beg questions. For example, in real life, if you kill the Dark Lord, you may just leave the way open for his more competent generals – fancy beating the 3rd Reich with Rommel at the helm?
 
Take any of the zillion stories about magic and magicians and dump them into a Techno Thriller. Yes, knowledge is power, but it's often undercut by stupid or lazy subordinates and contractors, else all space shots would be safe, and all super-tanks would work all the time, even during the Russian Winter.
 
In these stories, magic strips away the ifs and buts and takes you closer to the archetypal situation behind the story. Whereas Occam's Razor cuts away the unlikely, what I'll call "Merlin's Snake Oil", smoothes away with Von Clauswitz's friction.
 
Von Clauswitz's "friction" is the accumulation of little things going wrong so that nothing in war turns out as expected, and no situation is as stark or simple as it might appear just looking at the maps and the numbers.
 
I think this applies to other arenas as well.
 
With Merlin's Snake Oil, you can smooth away those bits of friction that mire your story in circumstantial detail. A magical single act really can destroy or save the world, impel your hero on a quest, or provide the ultimate peril.
 
This magic ungent is not just a useful tool, it's practically mandatory for Fantasy because it's what shapes the "What if...?"
 
What if knowledge really was power? What if you could save the world, but only by killing half of it...?
 
Looking at a completed Fantasy novel, which came first? It's seems conventional to expect that the author started off with a "What if...?" and hurtled skywards on a geyser of Merlin's Snake Oil.
 
But can you start with a powerful story idea and let the oil trickle down through the structure to form a "What if?" in the roots?