Termina é um "Mundo Paralelo", encontrado quando Link persegue o Skull Kid, em Lost Woods. (Ênfase minha):
Termina is the land where the story of The Legend of Zelda: Majora's Mask unfolds. After the events of The Legend of Zelda: Ocarina of Time, Link searches for Navi in the Lost Woods. However, he is ambushed by a Skull Kid wearing a strange mask known as Majora's Mask. Chasing after the Skull Kid, Link falls down a hole inside a tree, and wakes up in Termina.
[...] Termina is often thought of as a parallel world to Hyrule. This is never directly stated in the game, though the manual does call Termina a parallel world.
A rota direta para Termina nunca é explicitamente apontada para outro lugar, a não ser "in the Lost Woods". Já que o Lost Woods tem uma poderosa proteção mágica, diz-se que causa a perda irreversível dos peregrinos, a fim de proteger o Bosque Sagrado, onde vive a Grande Deku Tree.
it is said that if people wander in the forest for too long, they can turn into a monster
Quanto à conexão entre os dois jogos, o MM ocorre diretamente após os eventos da OoT , uma vez que o Ganon é cortado do Reino Sagrado. Navi sai, tendo cumprido seu dever, conforme estabelecido pela Grande Árvore Deku no início da OoT
Navi the fairy... Help Link to carry out my will... I entreat ye... Navi... Good...bye...
Citação da OoT - Depois de coletar a Pedra da Folha.
No começo de MM, Link está procurando por seu "amigo perdido". Esta é a Navi, como eles foram separados no final da OoT. Infelizmente, não há muito mais informação sobre este tópico.