How can I decompose a signal into square waves?
What is described in the question is very near the Discrete Wavelet Transform (DWT) with the use of the Haar Wavelet.

The DWT decomposes a signal into a sum of dilated and translated orthogonal functions that do not necessarily have to be trigonometric. The DWT does not transform a signal from the time domain to a frequency domain but to a scale space where the "time" dimension is preserved. The Haar wavelet is effectively just one period of a square wave and due to its dilation and replication as the transform progresses it would appear as occurring at different frequencies. For more information on the link between decomposition level and frequency please see this link

Another transform that might be of help here, is the Walsh-Hadamard transform which does exactly that, decompose a signal into a sum of square waveforms which are orthogonal (Please note the sequency there as well).

For a brief example that seems to be near what you are after, please see this link

Hope this helps.