Elevation and shape are obvious clues, but there are other factors. The crust is noticeably thicker than the ocean floor, for example, while the geology is distinct from other areas. Evidence of geological similarity surfaced early in the 20th century, when scientists noticed continental geology in rocks both in New Caledonia (at the north edge of Zealandia) and islands near New Zealand.
The question is, will Zealandia be widely recognized as a continent? The researchers are sticking to observable data and aren't speculating, but there's still a tendency to think of continents as being mostly above water. Even if it isn't broadly acknowledged, though, the findings help fill in more details surrounding the break up of the supercontinent Gondwanaland. Zealandia is estimated to have split off from Australia some 80 million years ago, and we now know that it never entirely went away -- it just sank below the waves.