Buenas noches Imrahil,

Siempre es más fácil una traducción al Quenya, porque hay un corpus mucho más extenso y una gramática más elaborada.
Como bien dice Tengvah, lo ideal es partir del significado del nombre a traducir y así comenzar.
Marina es el femenino de Marino, que proviene del latín Marinus, que quiere decir “del mar”. Vale, hasta aquí fácil ;-P

En Quenya, mar se traduce eär y una terminación femenina adecuada podría ser doncella (wendë, vendë, así como la forma corta wen), por lo que creo que una opción adecuada sería Eärwen (doncella del mar), que además es un nombre ya existente (hija de Olwë y madre de, entre otros, Galadriel o Finrod Felagund… nada más y nada menos).
Otras terminaciones femeninas genéricas quenya para darle más variedad serían: -e, -i, -ie, -iel, -më, -rë… Y éstas, que son más bonitas: tári "reina", aranel "princesa", heri "señora”.
Hay una página muy interesante de nombres traducidos en Quenya bastante completita (http://www.elvish.org/elm/names/m.html) que nos da otras opciones:
[quote]*earin, *earina […], por lo que se podría optar por Earina mismo (con un sonido similar) o Earine[/quote]

En Sindarin, “mar” aparece traducido por Tolkien de varias formas en diferentes momentos, sin quedar claro la forma definitiva (gaear/gaer/aear/aer) y doncella como elleth o iell, por lo que podría ser Gaerelleth o Gaeriel
Otras terminaciones posibles podrían ser: rîs "reina" (rien, rîn "dama coronada") o hiril "dama".

Saludos desde Tejonera.