Here's a good reference point: if you have one hard drive per camera, and record at 1Mbps, you can store 5 years of footage.
Stores have loss 'prevention' (more like tracking) software which the security team can use. They are able to attach images of people stealing, but its hard to identify a person from a camera 15ft away when they are bent over a shelf; so they attach images of them stealing and of them passing through choke points - e.g. checkouts and entrances.
Tying them together is laborious, and is currently in its own little model rush - it's a technique called re-identification.
However, the next question is why doesn't it happen in practice? Well the stores have found police to be uniquely annoying on that they won't arrest and the state won't prosecute despite clear evidence.