But you're right, they didn't do full cross validation. They performed a smaller scale validation where they trained on 80% and tested on 20%. Their writing is a bit muddled here, but it looks like 12 of the 16 novel associations (those not previously reported in literature) were validated (as in passed the above test). They did not perform validation on previously reported associations that they confirmed - presumably because they drew from an independent dataset from the original publication, and so this test constitutes an independent validation of the original study.
This motivated Columbia’s scientists to compare 1,688 diseases against the birth dates and medical histories of 1.7 million patients treated at NewYork-Presbyterian Hospital/CUMC between 1985 and 2013.
I immediately thought "hmm, tread carefully there fellas."