How many collisions (identical pairs) are possible in meet in the middle attack on double DES with two unique keys?
Now our job is to find all $x_i,y_j$ such that $x_i = y_j$. I suppose we can use $2^{56}$ binary searches so we could do this in $2^{56}\lg{2^{56}}= 2^{56} \times 56$ steps?

Actually, you're more likely to go with a hashing-based approach (which doesn't scale at O(n log n)), or a disk-based sorting approach (which is technically O(n log n), but a rather better constant of proportionality than repeated binary search); a binary search approach would run into a lot of cache misses (assuming you had that much memory).  On the other hand, sifting through that much data is a tad on the nontrivial side, and one we generally ignore when doing this high-level analysis; we simplify the problem by assuming that all computations, aside from the DES evaluations themselves, are &quot;free&quot;.
And, the 'steps' involved with doing this search for duplicates are quite a bit different than performing a DES operation (and are likely to be considerably faster); that makes it difficult to sum them meaningfully.
However, to get your real question:

on average the probability is that $x_i = y_j$ is $1/2^{56}$ right?

Nope; it's $2^{-64}$; that's because both $x_i, y_j$ are 64 bits, and can be assumed (with an incorrect key) to act completely random.

So now we have to check the $2^{56}$ candidate pairs

Nope; there are about $2^{112} / 2^{64} = 2^{48}$ expected
That should explain where the slide is coming from.