The titans themselves have souls, however, we have never seen any indication that the constructs like the earthen or iron vrykul, etc have souls.
Just like the elemental spirits don’t have a soul like mortals so to say, they are their own being.
Most likely they got it when they turned into their fleshy forms.
Like how we know dragons have souls yet they used to be elementals. But after exposure to the spirit element they turned fleshy and became proto-drakes, so it must have been the spirit element that transformed them and gave them souls.
Same with the orcs/ogres and that whole lineage, they originally came from a huge stone construct, that broke into smaller shards and after influence by the spirit element turned fleshy.
Now, what is the spirit element? It’s described as the fifth element, called chi by monks, what brings balance and harmony to the other elements of earth, fire, water, and air. It can cause plants to grow at an accelerated rate and even make them into so-called alive races like the Botani.
And most importantly it exists in all mortals and is the spark in their hearts that connects them to the other elements, which is what allows mortals to commune with them and be shamans.
Now what’s interesting is that there is a sixth element not often spoken about, called Decay which is the opposite of Spirit, it allows you to dominate the other elements and force them to your will, and is what dark shamans use to make the elements do their bidding instead of using Spirit. It’s actually shown on the cosmology chart of the chronicle book on the side of death. The shadowlands have also been described as a place filled with decay.
But other than that not much is known by the element, and I suppose it’s not really related to the question.
EDIT: I suppose I should add that creatures like the Mantid and Nerubians also have mortal souls. A Mantid even appear in the shadowlands, which is interesting as they’re descendants from the Aqir which is literally made from the biomass of the old gods.