He is not at the axe monument? Did you try walking around the house just south of there, keeping close to the walls? Sometimes he hides by a wall, and doesn't show up until you get near. There should still be a green cross on the mini-map for him, though, I think.
