The language sounds Russian, but I am not sure.
King Julian is not saying anything in any particular language.
If you mean the line after he asks Stevie if that's even possible, all he's saying is, "You naughty little thing," in a very shrill voice.
If you're asking about what he says after the line, "Stevie says," he's simply making a series of noises that is not supposed to be distinguishable. You're not supposed to know what Stevie is saying or what King Julien is saying he's saying.
Well, if I'm not mistaken, in the actual movie, there are subtitles for what he says after 'You naughty little thing'. I'm not sure exactly what language it's in, but the translation is: "Stevie says let them eat cake". You can find the transcript here, then scroll down till you reach that part. Or even better, just use control+f, to open the 'find' box, and search 'naughty'. It's the next line after the highlighted one.