A new, general method is presented to determine the equivalent linear span (ELS) of binary sequences having an interleaved or related structure. The method is based on a polynomial representation of the interleaved sequences followed by the use of the Euclid algorithm for factorisation, to yield a minimal polynomial. The degree of this minimal polynomial can be identified as the required ELS value. The method is then used here to show that the ELS values of the so-calledm-like sequences and the prime and relative prime interleaved sequences, proposed recently by the authors, are quite large and compare favourably with those of the bent function sequences.