It's Late Latin. From the OED:
Originally this governed a following word in the genitive, but in late Latin the tendency to use the phrase as a compound noun appears in vicequæstor (equivalent to prōquæstor of analogous origin). In medieval Latin such formations became common, as vicecomes, -consul, -decanus, -dominus, -princeps, -rector, -rex, etc.
As it mentions, pro was the more accepted prefix, though like vice- was also originally a preposition. The noun phrase later become codified and the preposition became a prefix. Examples: proconsul, propraetor, propraefectus, proflamen, pro quaestore.
I don't know of any Classical Latin titles with the prefix, and Lewis and Short record none under their definition of vicis.
My understanding is that the modern spoken Latin community doesn't like archaicisms like using consul for president, so they opt for Anglicized words. The ancients sometimes did that, but from what I read, they mostly did not. Considering the presidency was partially modeled after the consulship, I think a rendering of it as consul maior and consul minor would have made sense to a Roman audience, even if it's somewhat inaccurate.