Eyja is the genitive of ey - meaning 'island'. It's actually the same word as the 'is' in our word island, which explains why the 's' is silent (it comes an erroneous spelling modification in the 15th century). But ey=island is very familiar to us from the names of many an island, like Anglesey (Englishman's island), Sheppey (sheep's island) or Islay (island's island!), also the famous 'new-born' island of Surtsey, just off the south coast of Iceland.

http://languagelog.ldc.upenn.edu/nll/?p=2257#more-2257