Elekong can found completely at random in his "Phantom Oasis", which is found in Desert, just outside of Ita. It is quite difficult to find as it has a poor chance of appearing, and can appear just about anywhere. When it does eventually appear, walk towards it to enter the Oasis and go down the stairs. Talk to Elekong inside to recruit him.
Note: Keep continuously exploring the entire Desert area. To make it a little easier, clear the area of enemies and set Pommy Animal to "dash" through the Desert area. Contrary to popular opinion, Sharkun does not increase the chance of finding the Oasis.
With Elekong equipped, players can walk through soft blocks.