Was not able to comment due to lack of reputation points :), but the lemma about median laying on the diagonal is not correct (also for odd sizes of X and Y) so I think it's better to write it down in some visible place. Let's take: X=[1,2,3,4,5] and Y = [10,20,30,31,50]

The resulting matrix is:

11 12 13 14 15

21 22 23 24 25

31 32 33 34 35

32 33 34 35 36

51 52 53 54 55

The median will be by definition the 13th element (counting from 1) and when we sort X+Y we get:

11 12 13 14 15 21 22 23 24 25 31 32 32 33 33 34 34 35 35 36 51 52 53 54 55

32 is a median and does not lay on the diagonal: 15 24 33 33 51.

For the linear complexity algorithm we already mentioned paper can be used: http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf

While for O(nlogn) algorithm we have e.g.: http://euro.ecom.cmu.edu/people/faculty/mshamos/1976Stat.pdf

Either way very hard to figure out during the interview.