You have no storage problem. If anything, you have a problem of filling the available storage.
We have three spatial dimensions, a time dimension (completely different than the spatial ones, not least that we move in one direction only) and possibly some others.
Now you get another dimension into the mix. Leaving out what that dimension actually IS, everything has its scalar position in there. Maybe all non-soul particles are zero, while all soul-gas particles have some non-zero value. Note that everything still has the usual dimensions, so the soul-gas has (for the lifetime of the owner) the same spatial and temporal coordinates as the body. But in soul-dimension every particle has their own soul-measure. All the information storage you will ever need, right there.
Why does the gas need to do the same thing in soul dimension as it does in our spatial dimensions (i.e. be completely random in particle position)?
Every particle in the soul dimension has fix value, it is a crystal in that dimension. With a body-sized gas-cloud in normal atmosphere, you'll have ballpark 10^24 particles, each with their own, fix, soul-dimension-value. If the soul stores its information as a binary barcode (for some reason), i.e in the distances between soul-adjacent (not real-space adjacent neccessarily) particles, you could store 10^24 bits in there. That is Ten million one-terabyte harddrives.
That number grows if you do not stop at binary code, but go up: say its not one of two distances between particles, but particles can be any of a hundred measures from each other! Et Voila! You now can store 100^(10^24)bits in that soul.
While the soul gas particles do their wild dance in the real, in the soul dimension they are ordered and static.
One particle at 1 karm, next at 3 karm, next at four karm, next at five karm, next at seven karm - distances so far: 2,1,1,2, or 1,0,0,1 in binary, a nybble of soul if you will, if the soul is so gauche as to be binary....