I can very easily see these two getting together, even though I also love Hiccup and Astrid as they also work well together.
For the HTTYD and Brave crossover, it happens during the course of the Brave movie, Hiccup being chosen by his father to represent their clan in the "Viking Delegation" that's going to Scotland for the betrothal and marriage of the young princess, where the son of a clan chief in the region near Scotland will be taking part as one of the suitors. Hiccup is just there to represent their clan and give support, which will basically mean standing around and watching people probably make fools of themselves, but it's unfortunately one of those things that Hiccup will have to do when he's chief. The reason Stoic is having Hiccup go is so he can get some experience in being "diplomatic" with the other Viking clans; though Hiccup argues it's more like Stoic is making him go because the whole thing is probably going to be very boring. Still, Hiccup does as his father asks, flying to Scotland on Toothless to get there quickly, not interested in a sailing trip of weeks when he could easily get there in a few days by dragonwings.
Arriving in Scotland a couple days ahead of the rest of the Vikings, Hiccup actually meets Merida out in the wilds, Merida walking to a stream to get a drink only to discover a dragon doing the same. Merida is, at first, terrified upon seeing the dragon and accidentally draws its attention. To her shock, a young man about her age wanders into the area, calling out to someone by a nickname in his native Nordic tongue. Acting fast, Merida rushes to save him, firing arrows to keep the dragon back, which it dodges, before grabbing the startled young man and running away, knowing they are no match for the dragon, which pursues them. Things only get worse a few minutes of hectic running later when Merida attempts to have them hide inside some ruins, only to discover a massive hostile bear is already there and takes issue with their presence. Merida realizes the bear is Mor'du, and worse that they have nowhere to go, caught between the monstrous bear and the pursuing dragon. The two try to fight Mor'du, she with her bow and the young man, surprisingly, with a sword of fire, but they only hold the beast back. She's afraid both of them are about to die.
Then, to her shock, Mor'du gets attacked by the dragon, blasting a hole through the bear in a flash of purple light, before jumping into the ruins and pushing Mor'du back as the bear dies, standing between it and them. Merida's shock only grows when the young man relaxes and puts away his fire sword, thanking the dragon as he approaches and, unbelievably, pets it. Baffled, Merida wonders what is going on, having thought the dragon was going to kill them, but watches instead as it sniffs and looks over the young man, as if checking to see if he was okay, only to seemingly smile when it found he was.
Gathering herself some, Merida questions the young man about the dragon, but he only looks at her with a confused expression. For a moment, he tries to speak in Scottish, emphasis on tries, before giving up and switching back to Nordic, apologizing for not understanding her as he is still learning her language. Nodding in understanding, Merida speaks to him in Nordic (not exactly fluent at the language, but she knows it well enough), assuring he doesn't need to apologize and repeating her questions, wondering how he knows the dragon and why it protected them. He's surprised for a moment, but recovers, happy, and answers her, stating the dragon is his friend and that dragons, contrary to popular belief, aren't the monsters they are made out to be.
Seeing she is skeptical, the young man invites her over to meet "Toothless", which she is wary of, but her curiosity and intrigue win out and she walks over, extending out an empty open hand as she nears and lets the dragon make the next move. It does after it takes a moment to sniff her hand, rubbing its nose and head against her palm like one of the hunting dogs. Her fears almost vanishing, she spends the next few minutes bonding with the dragon, with encouragement from the young man, who introduces himself as Hiccup, and she does the same as simply "Merida". Her awe only grows when Hiccup offers her the chance to fly on Toothless's back, doubting when he claims to have ridden it before landing so Toothless could get a drink of water, but accepts when he climbs on and extends his hand, moments later finding herself high in the sky and soon among the clouds, hardly able to believe this is not a dream. Meanwhile, Hiccup is simply enjoying teaching another person that dragons are not their enemies, but their friends.
After a while, Hiccup has them land on a small hill where Merida spots and recovers her horse. Once adjusted back to the ground and soothing her horse, Merida asks Hiccup why he's in Scotland? Hiccup informs he's on the way to meet with the King and Queen of Scotland on his father's behalf, which he expects to be boring, but he accepts, enjoying the chance to travel to new lands. This news surprises Merida, but she doesn't press, instead offering to escort Hiccup to the castle, guessing he doesn't know the way. Hiccup admits he spotted the castle from the air, but won't turn her offer down, assuming they'll cause less panic if she is with them. Merida laughs and begins leading them towards DunBroch Castle.
When they arrive, the sight of Toothless indeed causes a stir, drawing nervous guards and her parents, but Merida waves off her parents' shock and concern as she pets Toothless on his neck, showing the dragon is far from dangerous. She quickly redirects their attention to Hiccup, who greet the King and Queen formally and apologizes for keeping his speech in Nordic, his Scottish being near non-existent.
This is when Merida gets her biggest shock of the day, her parents asking Hiccup what he is doing here, and Hiccup answering that he was there to represent his clan on his father's behalf during their daughter's betrothal and marriage. Merida instantly begins questioning her parents about this, and while Hiccup cannot understand what they are saying as its in Scottish, he is able to figure out that Merida is the princess, and that he apparently knew she was going to get married before she did. Hiccup speaks up, interrupting the heated argument going on between Merida and her mother, getting confirmation of his assumptions and taking Merida's side about the unfairness of the situation, especially with Merida having been kept ignorant until her suitors were already on their way. While Merida relaxes some, grateful for Hiccup's support, her mother argues that while he is right in that Merida should have been told sooner, the tournament and marriage will still take place, and hopes Hiccup will respect their ways and traditions like the other Vikings have. Frowning, Hiccup concedes, not wanting to cause a political incident, but gives Merida his condolences as she escorts him and Toothless to where they can stay for their duration in Scotland before she goes to preparation lessons with her mother. Merida manages a sad smile and thanks her new friend for his support and sympathy.
Over the next couple of days, for that is all they have, Hiccup acts as a friend to Merida, distracting her from her impending engagement when she is free, and inquiring about the upcoming events so he can understand and follow them; and secretly try to help Merida find a way out of it. The most he is able to do is add requirements upon Merida's suitors, making them need to perform individual tasks set by the Queen, the King, and Merida herself, along with a display of the suitor's talents and abilities so that they may impress and amaze her.
Soon enough, the three delegations arrive, and Hiccup takes his place among the Vikings, quietly standing back, as he is supposed to, and watches the events unfold. None of Merida's three suitors are outstanding, barely passing each of the tasks set upon them, if even that, not one a half-decent archer, and none performing feats that would have impressed Fishlegs or the twins. However, the Queen still calls for Merida to pick her favored among her suitors, forcing Hiccup to advance his scheme to Plan B: Declare that he wishes to compete as one of Merida's suitors as well, having been smitten by her spirit, brains, and beauty, that he cannot deny himself this chance to win her heart.
With his actions and insights, Hiccup argues he has already passed the Queen's trial testing the formality and intellect of the suitors. With his flaming sword, he can easily prove himself an accomplished fighter, as demanded by the King. With his shield-turned-crossbow, he is easily able to surpass the other suitors in Merida's test of archery. And as for his accomplishments and talents that would impress, he reminds that he is a dragonrider, of a Nightfury no less, one of the most fearsome dragons in existence, with whom he was able to slay the Red Death, a massive dragon that subjugated and devoured its own, allowing them to begin ending the conflicts between humans and dragons through peace and friendship. A feat of offers to prove, not with words, but with actions, and invites Merida to let him let her touch the clouds.
Shocked, but overjoyed, having a very good idea of what he's doing, Merida accepts, and, when they are high among the clouds, thanks Hiccup for everything he's done to help her get out of this arrangement. Hiccup assures he's just helping a friend and apologizes that his previous efforts didn't work, guessing the best they can hope for is to delay and give Merida time.
When the trio land once again, Merida gives Hiccup a bright smile; a clear sign that he is her favored suitor by far. Before the Queen can announce the decision and begin preparations for the wedding, Hiccup interrupts, apologizing, but arguing that they cannot move to those events yet, having gotten ahead of himself and, to be fair to Merida, wants to give her a chance to experience and accept the life she will have in the Archipelago before she makes her final decision.
Hiccup explains to the shocked King and Queen that, because he is an only child, his mother lost since he was a babe, his father having never remarried, and because of his needed presence in the Archipelago to train the other Dragonriders of Berk and bring peace between humans and dragons, he is incapable of becoming the King of Scotland when Merida and her husband ascend the throne when her parents step down, his responsibilities too vast and too important. Thankfully, Merida has three brothers, any one of whom could inherit the throne in her stead upon their ascension; should she choose to stay with him as Chieftess of Berk. Again, wanting to be fair, Hiccup wants Merida to have a chance to experience what her life would be like, as Hiccup acknowledges it can be hard and difficult.
Should she accept after this experience, at least one month of proprietary's sake Hiccup suggests, then they can return and all traditions and customs of a Scottish marriage will be upheld and respect, Hiccup confident a second ceremony and celebration would be waiting for them back in Berk upon their return. If she did not, than it would pain his heart, but Hiccup would accept Merida's decision, not wanting to force the lifestyle of his people upon others; a sentiment he is sure the King and Queen understand and share.
Taken aback by his valid arguments and honorable stance, the Queen especially, Merida's parents take some time to discuss the situation before agreeing with Hiccup's proposition. Merida, the Queen, and a small group of guards and advisers, less than a dozen in total, will travel to Berk and reside with them for a period of two months, meaning they will be gone for three as it'll take a month just to travel there and back by sea.
The rest of the celebration goes on mostly as planned, Hiccup apologizing to the Viking chief whose son lost, the chief someway sore with Hiccup, though the son privately admits he's not. When her parents aren't around, Merida again thanks Hiccup for helping her delay the marriage being imposed on her, hoping this entire incident will cause her mother to forget the idea completely and not start it all over again when she returns home in three month's time. Hiccup assures he was merely helping a friend and is grateful that his plan went over so well; although, he has a feeling his father won't be nearly as pleased.
A week later, the royal Scottish delegation sails for Berk, Hiccup and Toothless staying with them, most of their time being spent talking with Merida, partly the two friends continuing to get to know each other better, and partly to help Hiccup improve his Scottish, Hiccup believing Merida will have little trouble given her aptitude with Nordic displayed thus far.
A couple days before the ship reaches Berk, Hiccup and Merida fly ahead on Toothless, to ensure they are given a proper welcome they excuse. Hiccup and Toothless are welcomed back warmly by the villagers and Astrid and Stormfly, who saw them fly in, and Stoic, who grumbles about having had a feeling something had happened. Retreating to Berk's Great Hall, Hiccup and Merida explain what has transpired to Stoic and Astrid, assuring that this is only a delay tactic for Merida's benefit, Hiccup adding that aside from the formal welcome they will need to arrange for the Queen and the others, the people of Berk don't need to do or be told anything, quite confident simply being who they are and going about their daily lives will leave the Queen all too eager to return home when the two month's stay in Berk comes to a close. While not approving of the deception against someone so important, Stoic praises Hiccup for staying true to himself and his convictions, helping his new friend, and, less intentionally, securing a solid friendship between Berk and the next Queen of Scotland. Stoic and Astrid agree to keep their silence and go along with Hiccup's plan.
It's only over the next two months, primarily the second month, when Hiccup and Merida begin to develop romantic feelings for one another, Hiccup having simply enjoyed being back home, training with the dragonriders, learning more about the dragons, meeting new dragons, and sharing all this that he loves with his newest friend, while Merida has delighted in meeting new people, seeing new lands, making new friends who accept and embrace her for who she is and letting her do and be what she wishes, and, most exhilarating, finding and bonding with a dragon of her own, becoming the first Scottish Dragonrider. Even the political lessons Merida's mother continues to teach her, and the various tasks Stoic has Hiccup perform to help him prepare for his future role as chieftain, are more tolerable, more enjoyable, and easier with Hiccup sitting there beside her during the lessons and Merida helping him figure out how to solve the problem he's been tasked to fix. It's only after all this time together, and when they find themselves alone after flying out with their dragons, that they begin to feel something more than friendship towards each other, something more than mutual respect and admiration for their individual skills, brilliance, and abilities. And as the number of Merida's days in Berk grow fewer and fewer, and their kisses become longer and longer, the two find their dedication to their original ploy growing weaker, until Merida has no choice but to admit she wants to stay in Berk and Hiccup that he wants to marry Merida, having come to love and adore everything about her, as she has for him.
This is a much slower and more progressive romantic story than I usually image; and this is probably the longest of my pic-inspired story-posts I've ever written. But I still feel like it's a great premise for an initially-friendship romantic crossover story between these two characters. If anyone has read all my ramblings (first off, good job and thank you for getting through all this) and wants to take a crack at writing such a crossover fanfic, feel free to do so. My only request is that you leave a link to where you post it so I can read it, as that is something I would love to do, because I do NOT have time (unfortunately) to do it myself.