Interesting concept, with the ending somewhat foreshadowed.  Obviously the MC can't go back without transformation.  A pretty good plot, but very wordy.  It could be improved with some ruthless cutting.

 Blood had been cleaned from the Wanderer’s wirey hands,

That should be "wiry"

His knees were stiff from kneeling over the creature’s corpse, but he hadn’t wanted to touch the ground with anything but his iron-shod boots, at least not until he had gotten to the water.

He must have been kneeling on the corpse, not over it, if he wasn't touching the ground.

Water in this forsaken place was too hard to come by, he thought, and it was a waste to use it on something so trivial as washing his hands of blood, but something about that blood had disturbed him in a way blood never had before.

A too-long sentence, although establishing the dryness of the place he finds himself.  I am still trying to find a description of that place.  Maybe take out the "he thought" and make it at least 2 sentences.  "Water in this forsaken place was hard to come by.  It was a waste to use it for washing his hands, though something about that blood", etc.

 But even knowing he was only a thin veil of reality from home didn’t comfort him, for that sliver might just as well have been an ocean, and he would not return, not until he had found her.

I can't reconcile the "thin veil of reality" with the "sliver" that could have been "an ocean".  Maybe you could shorten the sentence a bit.  Also in this paragraph I have to leap from the waterless world to the "boat," a bit distracting.

The creature that had attacked him, and had forced him to kill it, against his will, was a Bonehunt wolf. Like most of the vile creatures that stalked this world, it fed on material flesh, and The Wanderer, being a living breathing human, was just what it had been looking for.

Both sentences are too long and many of those commas are unnecessary.  Maybe -- "He had been forced, against his will, to kill the Bonehunt wolf that had attacked him."  The next sentence is more complex than it need be, and somewhat repetitive as well. 

 The wolf sensed the presence of bones, full of juicy, pulsing marrow, and had come, coursing through the solid rock like it was water. The Wanderer had known it was coming, and did his best to prepare himself, but it had still managed to surprise him by lunging up behind him, catching him in a spray of human bones, which lay buried like roots with no trees.

Marrow doesn't pulse.  Both these sentences could use fewer commas.  The second sentence is, again, far too wordy.  However, this paragraph is essential to the understanding of the world he's in; we now know that the creatures "swim" through solid rock, and it's possible to relate his "boat" to that concept.

catching him in a spray of human bones, which lay buried like roots with no trees.

A nice image.

The creature was starved and desperate and had thrown all caution to the wind as it attacked savagely. It was too easy slaying it, but The Wanderer didn’t complain. Still, it was the first thing he had killed in this world where death was the law of the land, and as soon as he landed the killing blow, he felt something cold and sickly sink into his heart, clinging like a wet cloth.

Remove the cliche, please.  "It was too easy to slay it...".  And here is the first of several mentions of his heart as a material object.  

 Something was moving beneath him, shambling around below the boat.

Aha!  So the boat is afloat in the air?  Or is the little girl in the interior of the earth like the Bonehunt wolf?

 delighting in the hollow chiming of the bones bumping stone or glassy obsidian. 

low, melodic thuds of the bone on rock 

Chimes or thuds, I can't make this sound resonate.

The Wanderer listened to the low, melodic thuds of the bone on rock and found it soothing. He smiled to himself, even as his hunter’s instinct kicked in, warning him not to let his guard down, especially to something that seemed to offer him a modicum of calm. It did not escape his notice that no Bonehunt wolves or anything else came for her bones, and he assumed she had none.

Okay, so she's not alive in the same sense he is, but not this many words are needed to establish that.

Then, to his horror, she began to sing. Her voice – ethereal, as if it came from somewhere very far away, beyond mountains and across valleys hollow of vegetation 

Why is he horrified by her singing?  What are "hollows of vegetation"?

I like her little ditty, though. 

Her collected demeanor was a little off-putting; he had expected her to be either afraid or threatening, and her matter-of-fact tone threw him. 

I don't understand his expectations.  I would take this sentence out, as it doesn't add anything.

There was a silence. The girl didn’t seem to mind; she apparently had all the time and patience in the world. Finally, she asked, “Why are you here?”

To rescue my own daughter, killed by my own king. Instead, he said gruffly, “That is my business.”

Wordy.  Either shorten or take out the second sentence.  In the next paragraph, either add a "he thought" or say it aloud.  Finally, we know why he's there.

“Maybe I can help you,” she squeaked.

Squeaked?

The explanation that follows, of the difficulties of bringing someone back from the dead, does advance the story, but it needs to be trimmed down.

“You have a deal, Lily. I swear on the Wanderer’s pendant around my neck that, if you help me find the person I am looking for, I will return you to life, whatever the costs.” The sickly clinging in his heart got heavier.

Second time for that heart, but too many commas.

“There,” she said simply, pointing at a slanting wooden shack. “The House of Souls.”

The Wanderer stood up straight, for he had been stooping as he walked, and took in the legendary sight. In truth, it was wholly underwhelming. The House of Souls was the stuff of religious dogma and horror stories alike, and its name, if not its true nature, was known to every living person. It was here that all the dead went upon their demise, to await their judgment or to spend eternity in mindless anguish.

But it seemed far too small to contain the souls of all who had died since the beginning of time. It was no bigger than a lumberjack’s cabin, and far less sturdy. It leaned as if it were about to fall over and the boards of its walls were loose and hanging out in many places. The windows were cracked, though none were broken, and coated in smoky grime. The plains stretched out around the lonely shack, no variation except for the variety of bones protruding from the earth.

 She was only half joking, and he knew it. He forced a smile and kissed her, his usual, unsatisfactory response.

If he had been thinking, he would have kept his mouth shut and quietly retreated, but he was so shocked that the Wanderer called out. Thinking back, it seemed unusual that he would have called out Sarah’s name, as if he were in love with her, but that’s what he did.

As he walked back to the party, to celebrate his daughter’s birthday, a nagging doubt remained in his chest, like a wet rag weighing down coldly, engulfing and darkening his heart. But he ignored it, as he had always ignored his heart.