Any algorithm that requires you to compare each set to every other set is doomed to failure. It's an O(n2) problem.
The classic way around this is either minhash + LSH, or, if you only wish to detect near-identical sets of titles, simhash.
Both approaches reduce it down to an O(n.log(n)) problem. Both are statistically based: they are not guaranteed to find every similar pair above your chosen similarity threshold (though with minhash you can lower the threshold to increase the chance of finding highly similar pairs, then do further comparisons to strip out the pairs you don't want).
Minhash + LSH is relatively simple. Broadly speaking, it generates a set of, say, 50 hashes per user, and looks in a hash dictionary to see which of them are shared with which other users. Users that share more than, say, 40 hashes will have quite similar title sets. In your case, with tens of millions of users and a relatively small universe of possible features (movie titles), you should certainly not use minhash without LSH. Here's a good explanation of it.
Simhash is more complex to understand and implement, but it is faster and typically requires less storage. With simhash you'd generate only one hash per user, and the hashes are generated in such a way that small changes in the set of movie titles will result in only a few bits (if any) changing in the hash. The resulting hashes are then stored in various permutations in a set of tables cleverly organised so that very similar hashes (with small Hamming distance) will always be found in close proximity in at least one of these tables. Simhash has strict limits on how many bits difference can be detected: typically it is as low as 2, 3 or 4 bits difference in a 64-bit hash, depending on how the permuted tables are set up. So only very similar sets of movie titles will be detected.
Generating the simhashes themselves is pretty simple. Effectively you hash each of the user's movie titles to a (say) 64 bit hash using something like FNV-1a, then do a kind of bitwise average of all those hashes (see this explanation). The tricky part is solving the Hamming distance problem, without which simhashes aren't much use. Here's the paper explaining solving the Hamming distance problem. Edit: Not finding any clearer explanation online, I created this detailed explanation of near-duplicate detection using simhashes.