We study a class of Little String Theories (LSTs) of A type, described by $N$ parallel M5-branes spread out on a circle and which in the low energy regime engineer supersymmetric gauge theories with $U(N)$ gauge group. The BPS states in this setting correspond to M2-branes stretched between the M5-branes. Generalising an observation made in arXiv:1706.04425, we provide evidence that the BPS counting functions of special subsectors of the latter exhibit a Hecke structure in the Nekrasov-Shatashvili (NS) limit, i.e. the different orders in an instanton expansion of the supersymmetric gauge theory are related through the action of Hecke operators. We extract $N$ distinct such reduced BPS counting functions from the full free energy of the LST with the help of contour integrals with respect to the gauge parameters of the $U(N)$ gauge group. Physically, the states captured by these functions correspond to configurations where the same number of M2-branes is stretched between some of these neighbouring M5-branes, while the remaining M5-branes are collapsed on top of each other and a particular singular contribution is extracted. The Hecke structures suggest that these BPS states form the spectra of symmetric orbifold CFTs. We furthermore show that to leading instanton order (in the NS-limit) the reduced BPS counting functions factorise into simpler building blocks. These building blocks are the expansion coefficients of the free energy for $N=1$ and the expansion of a particular function, which governs the counting of BPS states of a single M5-brane with single M2-branes ending on it on either side. To higher orders in the instanton expansion, we observe new elements appearing in this decomposition, whose coefficients are related through a holomorphic anomaly equation.