Cluster very many sparse binary vectors
I don't think clustering is the right approach here. You want to merge them automatically, but clustering is too unpredictable for this; you need to manually examine clustering results.

I suggest you look at near duplicate detection instead. You want to merge documents that have a high overlap. There are some interesting - and scalable - algorithma for that. In particular, minhash (and later work) is worth looking at.