Thanks to Tsuyoshi's comment, I have the solution.
It's always possible to take some subset of lefts (of size k) and construct a set of k bicliques covering all the edges connected to those lefts (assign each left to it's own biclique together with all its right-neighbors). This means that for any subset of k bicliques in the minimum biclique cover, there are at least k lefts contained in the union of those bicliques.
Now we can construct the bipartite graph which contains a left node for each biclique in the minimum cover and a right node for each left node in the original graph. There is an edge between a left and right if the corresponding biclique contains the corresponding right in the original graph. The lemma above translates exactly to the criteria for Hall's theorem in this new graph which means there exists a matching which saturates the left side.
This corresponds to an assignment of bicliques to lefts in the original graph.