Ooh, thanks for the lyric quote Wilson, I'd not heard of that before.
The characters were great, the setting was great, the story was great. An Australian Weird West tell with mutated beasties in the Outback. I thought the descriptions of the songdogs were done well, I was given enough distinctive features (the serrated beak, black and white feathers, scorpion tale) to put together a reasonably good picture of them, but never quite enough details that they took an entirely solid form, instead their shape seemed to twist in the grasp of my mind, which was a pretty cool effect. I also liked how the other creatures were mentioned by name, but never seen (though the jackabox had a brief offscreen description, and the name gives a good connection there).
This reminded me a good bit of Cindarella Suicide for its Australian setting and wasteland beasties. It also reminded me a bit of some of the sub-worlds in the Otherland series by Tad Williams, particularly the... I forget what they were called, but they were a wraith-like dingo-like creature.