By couple I don't mean they are in a love relationship but that certainly might happen down the road. Just to be 100% clear I'm talking about man and woman here. The idea is that they start out as mortal enemies, then get thrown into a situation where both are out of their depth and have to team up to make it out alive. Alas a lasting partnership ensues. They begin as enemies because we first meet her and him on a battlefield as parts of two opposing armies trying to wipe each other off the map. The armies belong to different nations, hence they speak different languages.
There's a lot of potential here from a narrative point of view but as the story progresses there must be ways for them to communicate efficiently or they won't be able to survive. I imagine both to be of the "strong, silent type" as they are warriors as in experienced soldiers that have seen and done a lot that's not to be bragged about and that would mess up the minds of weaker willed people completely. They come to understand each other as being of the same breed.
Now the fact that they start respecting each other and share experiences that are new to either of them is a big incentive to start opening up and sharing. Just how would that happen when they aren't able to speak to each other?
Right now I'm leaning towards them both learning the language spoken in the place they end up at. I once had a semi-awkward experience where I conversed in an Asian language with a fellow European because I didn't speak his language well and he didn't speak my language or English at all, yet we had both learned the language spoken in the Asian country where we lived at the time.
But for them to learn the local language would be difficult to integrate into the plot as language-learning is a time-consuming process with flow-killing potential and their first attempts might just come across as awkward as my conversation with the European fellow in Asia. The awkwardness might make an already weird situation more believable though and few things lend themselves better to induce romance than to have the protagonists study together. It shouldn't become comic though as the undertone is serious. I can't imagine two elite soldiers going to school Harry-Potter-style! Them learning the local language would have the added benefit of being able to more directly engage with the locals.
It's gonna be fantasy so a magical element is possible. Magic could be used to speed up the learning process so as not to make it awkward. I'm open for ideas.