3x3 Eyes

The overall mood in each of these anime is dissimilar, but they share lead female characters that go from dangerous, and even evil, to sweet and completely innocent in a heartbeat. Both series are violent, Elfen Lied being much more so. Both anime develop a romantic relationship involving an ordinary boy and an extraordinary girl. 3x3 Eyes has a supernatural element that is absent in Elfen Lied's more realistic setting. The split personality of the main characters, and the problems they cause is the main reason to justify this recommendation. 

These old time anime have a gothic feel to them that only older works have and the main character deals with Demons.They also have the idea of a female sacrifice built into them. 

Both shows involve 2 main characters who are immortal and they want to become normal humans. If you liked 3x3 Eyes chances are you will like Mermaid Forest or vice-versa. 

The Anime deal with fighting off demons, not to mention the main male characters look alike and have similar personalities. There is also an air of mystery.  

Both of these series are Gothic horror from the 1980s with classic horror elements, but with a main female protaganist. 

Before there was Inuyasha and Kagome there was Fuiji and Pai. Except, in the case of Fuiji and Pai, the demon is in fact the female companion rather than the male, yet the search for becoming human or instead searching for demonic power is a common thread in both series. The artwork is dark, but the tone of the narrative has the same felel. 

Both anime are dark supernatural anime. The main protagonist (Yakumo Fuuji in 3x3 Eyes and Kei Nagai in Ajin) in both titles are immortal beings that can not die. The main protagonist in both titles got hurt in similar a deadly accident and end up finding out that they are immortal. The main protagonist in both series has a friend on their side to help them out. Both titles have action, violence, blood, and gore with a very dark and gritty atmosphere. If you enjoyed one, you will enjoy the other.  

Both titles deal with the main protagonist who is aided by a powerful demon (Pai in 3x3 Eyes and Tora in Ushio & Tora) to fight against evil supernatural forces. The biggest difference between the two is that 3x3 Eyes is more violent and darker compare to Ushio and Tora. If you like one, you will enjoy the other.  

Both "3X3 Eyes" and "From the New World" deal with human identity and with the relationships between humans and "the supernatural". The female leads from both shows struggle with psychological afflictions caused by magic. 

Perhaps one could call 3x3 Eyes the granddaddy of Zero no Tsukaima. They share the same premise - good-for-nothing local boy becomes the servant/slave of a girl with magical powers with whom he fights monsters and bad guys. Each of the male leads is equally reluctant to accept his new position, though, adapting seems to be the only hope to get out of it. Moreover, both shows nicely point out these guys' desperation over having lost their old lifes and missing their home. The main difference between the shows clearly lies in their tone. Despite both of them containing a fair amount of fan service, 3x3 Eyes takes itself way more serious. Zero no Tsukaima comedically exploits its more stereotypical characters like the female lead Louise, who is a true tsundere. Her counterpart Pai from 3x3 eyes shows the same traits because of a split personality only, where one part is a quite likeable deredere character. read more 

A boy is saved from death by a girl through extraordinary means, in the process linking the two of them together. These OAVs don't share a ton in common beside this plot point/premise, but if it sounds appealing to you you'll probably enjoy both of these, as they're rather good. 

Devilman and 3x3 Eyes feature two protagonists that must fight against evil powerful demons. Both anime were released in a similar time period (late 1980's - early 1990's) and shared a similar dark and gritty atmosphere. They are action-packed anime featuring violence, blood, and gore. If you liked one, you'd like the other.  

The Anime are similar in style and the main female character who runs next to the main character is very similar as well. The story is dark and the animation is an old school Gothic style. 

Both come from the early 90's so have similar animation styles. Both deal with the supernatural, demons, and magic. They are gory and violent. 

The main character of Kurokami, Kuro, is very similar to Pai in 3 x 3 Eyes. Both characters have a cute/playful side but they also have a dark/dangerous side. In terms of story the shows are also similar so far. An event that occurred in episode 2 of Kurokami reminded me of 3 x 3 Eyes start. I can't say more without spoiling the second episode of Kurokami.  

both have supernatural being where they turn humans into an immortal to protect  

The plot lines involve fighting off demons bent on bringing destruction to man kind. The anime also take into consideration actual legends about various monsters from around the world to make the stories work.  

Both anime are OVAs from the early 1990's with similar animation and a similar vibe. Both titles deal with the main protagonist who is aided by a powerful demon (Pai in 3x3 Eyes and Tora in Ushio & Tora) to fight against evil supernatural forces. Both anime have plenty of action, however, 3x3 Eyes is darker and more violent compared to Ushio & Tora. If you like one, you will enjoy the other.