Due to their ever-increasing number of applications, multi-label classification algorithms are facing a major challenge: learning from evolving data streams with distribution changes over time, under limited computational and memory resources. In this paper, we first revisit existing works through a meta-model of low-complexity multi-scale algorithms combining short-term memory for fast drift adaptation and long-term memory to integrate distribution changes over time. Then, we develop a very strong baseline from this family, called A2ML (Adaptive Memories for Multi-Label stream classification), specifically designed for non-stationary streams. Its long-term memory is managed via adaptive label clustering and biased reservoir sampling, ensuring linear-time model updates. A2ML is compared to 7 state-of-the-art algorithms on 15 stationary and 4 non-stationary streams with over 100,000 examples, generated to test various data changes and concept drifts. Results show A2ML performs well in both settings and has lower computation times than competitors.