How can a recommender system manage to calculate similarity between 10m users and get recommendations of similar ones?

It's tricky to do fast if you want the MOST similar ones because you will have to go through n^2 calculations
 
If you want similar enough you can use a large enough subset of users to get similar users which will reduce the computation time
this kind of operations are easy to do in parallel too since each user is independant