A looooooong time, haha. Actually, I had collected most of the souls already, having beaten the game 9 times, so I was only missing 18 when I actually started looking. I only needed to search for like 2 hours to get the ones I still didn't have. There are some annoying ones. The poison worm took me about an hour of repeated kills and apparently, for the mandragora, you can't just kill the skeleton. You have to kill the actual plant after he pulls it out of the ground, but before it explodes. The arc demon took forever too.