The souls can be farmed from new mobs after you beat wall of flesh. 

So far I have found soul of flight witch is collected from dragons. I found the dragons on my path I made for collecting stars, near the top of the world, where grav has less effect.