Here’s what Yamagami and Ando had to say about the situation, as translated by kantopia:
Please tell us what led up to the planning of Tokyo Mirage Sessions #FE.
Yamagami (Nintendo Producer): 5 years ago, Ms. Ando proposed a plan [for a crossover], saying “You know, I think FE and Pokemon‘s rules are pretty compatible!” Though I agreed with her, by chance the Pokemon group had already proposed what eventually became Pokemon Conquest at the same time [so we were unable to follow through].
Ando (Nintendo Director): Yes, which I was in charge of too.
Yamagami (Nintendo Producer): As the plan was a secret, she was put in charge of that first. (Laughs). And then, it took her less than a week to say, “Here’s the next plan.” The new plan was a collaboration with Atlus. At that time, new games like Xenoblade and Pandora’s Tower were coming out, and, because I myself was quite interested in Atlus’s games, I figured “This could work!” At first, we made informal plans within our own small group, but…
Takata (Atlus Producer): At that time, the organization itself was undergoing changes. and it was almost impossible to deal with Atlus as a second party, and so we almost decided to give up on it. After roughly 2 years, we heard from Hiraoka (board member at Atlus), “Let’s try to collaborate and level up by making an RPG together.” After that, we attempted to contact Nintendo repeatedly, asking “Do you want to bring that RPG to life [with us]?”
Yamagami (Nintendo Producer): We replied immediately with, “Let’s do it!” We then quickly began to draft plans for the game, still only having a rough idea of what it would be. And so, we released an image that showed, “Shin Megami Tensei Meets Fire Emblem” to the public.