All language is merely encoded information so theoretically speaking, this is an engineering problem pure and simple. But to break it down;
First you have to know that the cilia (small hair like tentacles) are actually moving according to a set pattern and that it contains information, like the skin colour. In other words, you have to be open to the idea that anything could represent communication, not just sounds or images.
Next, you have to find a 'crack in the ice', so to speak that allows you to grab on to a single concept and how it's represented. Then you use that to build out new concepts. In xenolinguistics, it's almost universally thought to be math that will be used as that crack in the ice because mathematics should be universal in concept, but would be represented in a manner that is unique to the race or species expressing it.
Finally (and this is actually the easy part) your engineers generate a box that can display different colours and patterns, and have some mechanical cilia on top that can act as an interpretation device. Ideally, you have another machine that's a camera and translation program that can take colour an cilia movements and translate that into a mechanical voice, or even just text.
The novel Contact by Carl Sagan (also a movie, but the book's better) explains how to use math and science to get that crack in the ice with a message from aliens. Also, the movie Arrival (also based on a short story) actually does a pretty good job of representing how a linguist would try to communicate with something utterly alien to us. Forget the whole time perception part; language can't do that but linguistics is all about breaking down the language structures we all take for granted and tying the elements back together with a new symbology that both parties can now understand.
Depending on how many cilia are involved in Atlantean communication, humans might be able to approximate it with their hands. There's also the possibility of actually wearing the light box on their chests, to make the communication look as natural as possible. Of course, all this implies that the aliens actually WANT to talk to us. Working out a common frame of reference for communication between two species as diverse as described here requires patience on both sides. If the other side is also willing, communication will come because both sides want it and are not obfuscating to hide their language. In such a case, just flashing prime numbers via a light (2 flashes, rest, 3 flashes, rest, 5 flashes, rest and so on) would be a great place to start, because the Atlanteans (if they want to talk) will start demonstrating the patterns they use for those numbers as the flashes are on.
At the very least, that's where I'd start.