I think the possibility of being in a relationship, which didn't work before, but you are trying again anyway has good parallels with the mooted idea that the main characters' repeated erasings, reconcilliations, next-attempts and subsequent break ups.
It's more extreme in the story's case, since rather than 'just' breaking up, they are trying to stop the person from ever having been part of their life, but it's the same, doomed, process.
As for the sci-fi/non-sci-fi, the film needs the macguffin (mcguffin?) of the erasing process for starters but the charm of the film, and the point of the film if you ask me, is the characters and their stories.
It (the getting rid of memories/history) element could equally well happen in a *spits* magical realism genre.
Same way Star Wars is sci-fi since there is clearly such a great love for the technology used in the film (not to mention that it needs space ships and death-stars, but even then they are not 'just' included: the writers and audience enjoy those elements in themselves), in Eternal Sunshine I would say that the audience's and the writer's interest is in the people, rather than how the erasing process works.
*runs away from the gaping, endless maw of 'what is sci-fi' debate*
