The Genie comes off from a magic lamp, then turn into coins while laughing. It appears in a hidden area on the second mission that is very tough to reach, as it requires precise jumping.
Given his context, it would've made more sense if he appeared in the first mission, since he is based on a tale from 1001 Arabian Nights. His design is based on the Genie from Disney's Alladin.
The Genie also appears in Metal Slug Attack on cranks if the player gets a unit (or 10/30/80 parts if they already have that unit). As a result, he will almost always appear on the 10x Medal/VIP Crank. A golden variant of him can appear in the Box Crank if the player pulls 30 parts of the featured unit.
Rough picture text translation
The Demon King will answer to one's curiosity. His favorite words are "Watch your head" and "Haste makes waste"
Watch your head is in reference to the poison trap hidden above the players head.
Haste makes waste refers to collecting the lamp too early only scores 10 points, instead waiting for the genie to appear scores a big amount of coin points