I've thought about this more, and I think my question could be answered. So, here goes.
The troll is a... drum roll please... crocodylomorph!
Evolutionary history of the trolls (Family Macronasidae):
11.8 million years ago, in Miocene South America, "super crocodilians" terrorized land and water. There was Charactosuchus, a giant gharial, there was Purussarus, the strongest crocodilian ever to evolve, there was Mourasuchus, a filter-feeding planktophagous crocodile.
But on the land too, there were more "super crocodilians" - namely Barinasuchus arveloi, quite possibly the largest terrestrial carnivore in the entire Cenozoic era. It was a sebesuchian - a relative of the crocodilians - and has been referred to as "an ecological vicar of the non-avian theropod dinosaurs".

Barinasuchus on the hunt. To give you a sense of scale, its prey is Xenastrapotherium , about the size of a black rhinoceros. Image source: Jagroar on Deviantart
Unlike its semi-aquatic relatives, it had long legs suitable for running. Laterally-compressed jaws crushed prey, and it was so reminiscent of predatory dinosaurs that when scientists found its teeth, on their own, they thought that the theropods had survived into the Miocene.
Enough about the facts, now for speculation.
The Miocene-Pliocene extinction nearly wiped out the sebecosuchians (The branch of Barinasuchus). However, some populations of Barinasuchus survived, but they would not remain apex predators for long.
For the first time since the Cretaceous period, South America was invaded by fauna from the north. Carnivorans like the short-faced bear and saber-tooth cats drove most of the already-declining crocodylomorphs out of their niches at the pinnacle of the food chain. The crippled populations of Barinasuchus fled from the great savannas which the carnivorans ruled, and found refuge in isolated patches of forests that were springing up as a result of the cooling climate.
During this time, some Barinuchus learnt to hunt birds, which sometimes led them up trees in search of their prey. Eventually, they would become more accustomed to life in the trees, despiting showing little adaptation for it (Besides slight dwarfing). An example of this in the real world is the tree-climbing goats of Morocco:

In Morocco, many goats climb trees, despite not being adapted for it in any way. Image source: CBS News
At first, the arboreal creatures behaved almost like arboreal lizards, gripping the trunks of trees with their bellies pressed to the bark. Eventually, evolution took its course, and in millions of years, the ex-Barinasuchus became a new family, Arborisuchidae. The long legs of the terrestrial crocodile had helped it, now becoming strong arms for climbing. The crocodilians had taken on an almost primate-like form.
But the climate was still cooling, and now the lower rainfall in the ape-crocodile's habitat was making vast swathes of forest turn to grassland. The creatures migrated northeast, where there was tropical rainforest.
The cooling climate continued to take its toll on the last of the mesoeucrocodylians, but one resistant population took up living in the swamps and marshes around river mouths in their South American home.
Some days in these great rivers, mass floods would uproot tree after tree, creating vast floating mats of logs and vegetation. This still happens today in the Amazon and many other rivers:

Gigantic "rafts" of logs can contain entire mini-ecosystems. Image source: Getty Images
Often, animals will jump aboard these massive rafts as they pass by, for protection, food or merely curiosity. Then, the log mats get washed out to sea and may sail across oceans. In this way, many alien taxa of animals colonize faraway lands - indeed, this was possibly responsible for the majority of Madagascar's entire megafauna.
The arboreal crocodylomorphs also boarded these rafts on occasion, and the currents of the Atlantic Ocean brought them to Europe. While the ape-crocodiles of South America died out due to predation, these European crocodylomorphs occupy the only large semi-aquatic niche in their ecosystems (A slot occupied by the caimans in their old home), so they flourish.
Europe's climate is much colder, so they evolved large, pointy noses to process warm air. A real-life example would be how humans evolved their noses when they moved north, whereas our brothers in the tropics have flat faces. These semi-aquatic trolls came to behave very like their cousins in the order Crocodilia, the Nile crocodiles (Crocodylus niloticus). They evolved long, filamentous integument called pycnofibres, a structure seen in pterosaurs (I picked pycnofibres because crocodylomorphs are Archosauriformes too), that looked like river weed, and long arms for grabbing prey. They were so derived from their ancestors that they became a new family, Macronasidae.
When the glaciers of the last Ice Age receded, some trolls migrated north to live in the wetlands of Scandinavia, evolving even more cold-climate adaptations like even bigger noses, more hair and stockier builds.
The Macronasids behave quite like their cousins in the genus Crocodylus, in that they conduct water-to-ground predation. When a deer, goat or sheep comes to drink at the water's edge, they explode from the water and grab the prey with their long forearms. Instead of the elongated, fish-snaring jaws of other crocodylomorphs, theirs are truncated to deliver powerful, killing bites to still their thrashing victims.
They sleep, give birth, nurse and defecate in the water, like hippopotamuses. In fact, they spend almost all of their time half-submerged, sometimes emerging to bask in the sun.
Please let me know what you think of this theory, and I hope you like it. If you think you can best this answer, by all means do, for I am still open to other suggestions.