In this paper we propose a new parallel algorithm, ESPRIT-Forest, which is able to handle the problem of hierarchical clustering of tens of millions of sequences accurately, with subquadratic time and space complexity and a good scalability with respect to the number of CPUs.