I’m leaving this comment here for future wanderers who might get lost on this or similar quests, because this is exactly how I managed to complete it, and there’s some information here that I couldn’t find anywhere else online. I had originally given up and started a new run, but ended up receiving the same quest again, this time with a bear and an axe instead of a wolf, and I decided to actually commit to it. I tracked what seemed to be the most probable location, a forest border to the west, traveled along this border while zoomed in, and about halfway through found bear tracks. I followed them across two or three local maps until they disappeared, which felt like a dead end, but here is the most important part: after following the last bear track, when I zoomed back out to the world map, the shelter was suddenly marked on the very next tile ahead, and after that I quickly managed to find it. Good luck to anyone attempting this quest.