The Lubavitcher Rebbe (here - third paragraph) quoting the Previous Lubavitcher Rebbe, tells a story of the Alter Rebbe (the Baal Hatanya) in which he (the Rebbe) mentions that the Alter Rebbe didn't hold his hands behind his back al pi kabbalah. This wasn't even referring to folding one's hands, let alone walking.
The Alter Rebbe was warming his hands by the stove in the back of the room while looking and listening to a conversation in the front. Nevertheless, the Rebbe says, he was careful not to put his hands behind his back, but at his sides. Since the Alter Rebbe lived 1745 - 1812, this story took place before the Ben Ish Chai was born (1833).
An anonymous comment here says that in another one of the Lubavitcher Rebbe's seforim (perhaps here, can't find an online copy) there is a footnote by the place where the Rebbe mentions that not putting one's hands behind one's back is kabalistic: "
(ראה שער רוה"ק דרוש א' הב' (קרוב לסופו". Despite spending some time looking through that sefer, I was unable to find the source, although I didn't fully understand the above footnote, so perhaps I was looking in all the wrong places.
Significantly, this predates the Ben Ish Chai, is an example of a prominent personality being careful about this, and would also seem to debunk R. Aviner's assertion that it is superstitious.