> I walk & work out a lot and I'm finding a lot of the running/training type shoes wear out in 3-4 months,

Not for running, but for almost everything else, Vans and Chucks will last a lot longer. They are great for squatting as well! (100% contact with the ground)

I put a lot of miles on each pair of Vans, they last me ~2 years before the sole gives out, the fabric starts to rip at about the same time.

Anything from Ecco will probably last. I've also never seen any of my Keen stuff fail. Both brands are rather expensive.