Deep extreme multi-label classification seeks to train deep architectures that can tag a data point with its most relevant subset of labels from an extremely large label set. The core utility of extreme classification comes from predicting labels which are rarely seen during training. Such rare labels hold the key to extremely personalized yet relevant recommendations that can delight and surprise a user. However, the large number of rare labels and extremely small amount of training data per rare label offer significant challenges, both statistical and computational. The state-of-the-art in deep extreme classification tries to remedy this by using label metadata such as textual descriptions of labels, but fails to adequately address the problem. This paper presents ECLARE, a scalable deep learning architecture that incorporates not only label metadata, but also label correlations to offer accurate real-time predictions within a few milliseconds on commodity hardware. The core contributions of ECLARE include a frugal architecture and scalable techniques to accurately train deep architectures along with label correlation graphs at the scale of millions of labels. In particular, ECLARE offers predictions that are up to 9% more accurate on both publicly available benchmark datasets as well as proprietary datasets for a related products recommendation task sourced from a major search engine. Code for ECLARE will be made available on a public repository.