I'm also a big fan of Fate and Magic the Gathering, so here's to hoping I do your question justice!
Balance and Feasibility
To answer some of your concerns first, I will say that such a system is totally feasible and can be "balanced" just fine, as long as you and your players all agree upfront what it should look like, what the limits are, and how common it should be. Fate handles tweaks, modifications, and homebrew spectacularly well (it's basically designed for that), so the limiting factor is generally what everyone at the table actually thinks is fun.
For instance, if only one player is at all interested in summoning, and the party never faces anyone who does it, that player might A) seem "better" than his comrades if he and his summons get to act each turn in Conflicts, Contests, and Challenges, and B) get frustrated that the game is so much more complex for him than everyone else!
On the other end of the spectrum, if everyone and their mother in your setting is waltzing around with a small army of Goblin Tinkers (all exchanging Ornithopters for Darksteel Golems every turn, of course), the complexity problem might rear its head in a different form: turns take so long for everyone and their forces to act that you feel like you're playing a plodding wargame rather than an exciting RPG based around action, inventiveness, and collaboration.
If your players are interested in doing this, and you all agree upfront how complex and powerful summoning should be to fit your desires and goals, then there is no problem implementing it. You don't need to be concerned about it "only" costing a Stunt, Skill, or Aspect, if it's designed around the amount of cost you assign it. In fact, depending on how powerful and common it is, playing with the cost involved (maybe it sucks up Refresh, an Aspect Slot, and a relevant Skill!) is a great way to keep it from overwhelming other skills and ways of playing the game.
Unless, of course, it's your intention to have Summoners stomp all over paltry swordsmen and politicians and songwriters and whatever other kinds of "classes" are common in your gameworld!
The "Storm Summoning" System
First and foremost, I'd suggest giving the Storm Summoners magic system proposed in the Fate System Toolkit a read. It plays with the notion of summoning in Fate by tying it to elemental "storms" of power inhabited by creatures who can be summoned or bargained with through the use of a "Conjuration" skill.
As a brief summary: for basic summons, you roll against the power of the elemental you want to summon (from Average [+1] Wisps up to Great [+4] Attendants) as a Create an Advantage Action requiring material components. Success grants you control over the creature for a set amount of time, while failure summons an uncontrollable elemental.
The skill is also used to attack (banish) other conjurations or to defend against their attacks with magical wards, as well as to renew existing summons. The total number of summons allowed is also determined by your skill.
The summons generally have only one skill (___ Elemental) used for any action they could reasonably accomplish specifically by being one (e.g., fire attacks, walls of ice, control of water, etc.). Smaller ones are weak, but have bonuses to speed-related skills, while larger ones have more Stress and Consequence slots. Each element also grants an additional ability (e.g., Fire grants a Weapon:x rating, while Earth elementals have more Stress boxes).
If a character makes a lasting (and expensive) bargain with a specific element, he gains bonuses when summoning it and gets access to even more powerful (+5 and higher) summons. This bargain is usually represented, mechanically, by an Aspect denoting it, which of course can be invoked (bonuses on conjuration rolls) and compelled (being forced to do work for your chosen elemental storm).
In combat, the Elementals use teamwork rules like Mooks (strongest one sets the base attack power, others act as +1s), and can aid the summoner on Skill rolls that make sense or be sacrificed to "absorb" blows on behalf of the summoner.
Specific M:tG Tweaks
The first obvious tweak is to replace the elements with the five colors of Magic, or whatever other obvious power-separations make sense in your own setting (I'd start there; save multi-color or similarly complicated summoning for later revision or see if it's necessary at all).
You can then tweak the summoning specialty chart, as well: Maybe Red-aligned creatures gain a bonus to Athletics or a Weapon rating, while Blue-aligned creatures can be sacrificed to banish an equally powerful-or-weaker creature controlled by someone else, for instance.
You might also consider replacing the single Conjuration skill with separate ones for each flavor of magic in your setting. That's more complex, but my guess is, if you want to have summoners running around arenas trying to bash each other to bits with giant gorillas and the like, players in the game will want to be as cool and unique as possible while doing so!
In that case, you can modify the skill's usefulness from just Summon/Banish/Defend against Elements to more flavorful uses. Perhaps White Magic replaces Lore/Medicine/etc. as the default Skill used to recover Physical Consequences with an Overcome action, or maybe the Black Magic Skill gets a Stunt to take Stress in order to increase your rolls with it.
For easiness' sake, I would strongly recommend you keep up the idea of having all summons act as a mook mob (single action per exchange), particularly if the party will have or face multiple summoners (in fact, if everyone is going to be summoning, I'd even consider allowing a Summoner or his summons to act each turn, although still granting each other Teamwork bonuses when not "in use.").
Artifacts could probably be represented by Extras (built using the Golden Rule--a Cloudpost artifactor even Stunts
