Borrowed from Medieval Latin ultrāmarīnus, from Latin ultrā (“beyond”) + marīnus (“of or relating to the sea, marine”). By surface analysis, ultra + marine.
Noun sense 1 (“pigment”) refers to the fact that lapis lazuli was obtained from foreign countries and hence “beyond the sea”.