Doubt regarding Maximum Bipartite Matching
Here's one possible hint:

$$\gcd(u,v,w,x) = \gcd(\gcd(u,v),\gcd(w,x)).$$

I expect your problem can also be solved using the techniques in the following paper:


Daniel J. Bernstein. Factoring into coprimes in essentially linear time. Journal of Algorithms 54 (2005), 1--30.




A maximal matching doesn't seem like the right approach.  The maximal matching algorithm you list will never choose two 4-tuples $(u,v,w,x),(u',v',w',x')$ such that $(u,v)=(u',v')$.  Thus, it won't produce the correct answer to the problem: it won't output the maximum number of different 4-tuples.