Locathah were always a favourite of mine. If you want real evil, go sahuagin.
Let me just check my Realms Charts (a system I developed for creating realms of ALL kinds from tribes to cities to forests - it includes large race lists inspired by the 2E World Builder's guidebook).
Here is a list and their refs:
1. Aventi - 3E Stormwrack (Atlantean-like ancient people - might be perfect).
2. Sea Kin - 3E Races of Destiny (Also 'altered' humans, a little more creepy from memory).
3. Merrow - D&D most eds inc Pathfinder (Aquatic ogres).
4. Scrags - D&D most eds (Aquatic trolls).
5. Elves - D&D most eds had a sea-styled elf.
6. Crabfolk - can't recall, but it was D&D. 2E.
7. Darfellan - 3E D&D Stormwarck (Orca folk with heavy NW Native American influence).
8. Kopru - 3E MM2 (Eelfolk but nasty)?
9. Kuo-Toa - D&D all eds (Underdark fishfolk).
10. Locathah - D&D up to 3E (Fishfolk and a fav I would like to use more).
11. Nommo - D&D 3E African Adventures (African fishfolk).
12. Sahuagin - D&D all editions (Sea devils).
13. Shalarin - 3E Forgotten Realms (I believe a warped version of sea elves, that weren't so good).
14. Anguillian - 3E Stormwrack (lamprey-like folk).
15. Ixitxachitl - D&D most eds (evil intelligent, devil-worshiping rays).
16. Ormyrr - 3E MM2 (Not sure - I think intelligent worm-like things).
17. Sea Wolves - 3E Stormwrack (No explanation needed...right).
18. Tako - Oriental Advs (inc 3E) (Octupi-folk).
19. Sharkfolk - Pathfinder from the Skulls & Shackles AP I believe.
20. Grindylows - as above (basically goblins cross octupi I think. These 2 are from mem of the minis - I need to actually add them to my lists).
22. Tritons - early D&D (basically another version of merfolk with legs and separate fins).
22. Star Wars Alien: yes I have done this regularly. I have used several aquatic species in my games. Some art even looks fantasy. Best bet would be Aqualish or Nautolans, but could also go with Quarren or Mon Calamari
23. Many other 'folk' mostly developed for fresh water, or at least coastal waters, such as lizardfolk, kappa/tortles (turtlefolk).
24. Or Google merfolk for a heap of cool variants. Some great art out there inc some great eel-like pics by Applibot. (I just saved those pics and will HAVE to create a race for them now

).
That should about do it
Good luck
