The most widely spoken languages in Melanesia (excluding the part of Indonesia that's in the region) are English (duh), French (in New Caledonia, which is owned by France), an Austronesian language called Fijian spoken in Fiji, and three English-based creoles called Tok Pisin (in Papua New Guinea), Bislama (in Vanuatu), and Solomon Islands Pijin (in the Solomon Islands). However, there are many, many more languages spoken in these countries. East Fijian is the official language of FIji and closely related to the Polynesian languages. West Fijian is much more marginalized and a bit more distant from both Polynesian languages and East Fijian. Fiji Hindi is a language spoken by the Indian community of Fiji and derived mainly from Bhojpuri as far as I understand.
One useful website for an introduction to the languages of Papua New Guinea, the most linguistically diverse country in the world, is
this. It has resources for many (if not all) languages spoken in Papua New Guinea.
One language that I started learning a bit of through that website is Waris. Waris is spoken in northwestern Papua New Guinea, near (and to a lesser extent across) the border with Indonesia, and is in fact part of a small family of languages spoken in roughly that area known simply as the Border languages.
The largest in terms of number of speakers is Enga, which is part of a small family that's usually classified as being part of the Trans-New Guinea family. It's spoken in the middle of Papua New Guinea in Enga Province. Enga has even more native speakers than Tok Pisin!
Unfortunately, I don't know anything else about Enga, really, but I do know a few words of Usan a.k.a. Wanuma, which is spoken in Madang. Madang is just to the northeast of Enga Province. The Madang languages, which are spoken there and include Usan, are generally considered to be part of Trans-New Guinea. They include the Croisilles languages, which in turn includes the Numugen languages, of which Usan is a member.
One common feature in a lot of Papuan languages is switch-reference, and it's illustrated in these two sentences in Usan (courtesy of
The World's Major Languages):
Ye nam su-ab, isomei. 'I cut the tree and went down.'
Ye nam su-ine, isorei. 'I cut the tree, and it fell over.'
(
ye 'I',
nam 'tree',
su 'cut',
isomei 'I went down',
isorei 'it fell over, went down')
In these sentences, -
ab indicates that the subjects of both clauses are the same (I'm the one who both cut the tree and went down), and -
ine indicates that they're different (I'm the one who cut the tree, but it was the tree that fell down).
Another one of the Madang languages is Manat a.k.a. Paynamar, which is part of the Southern Adelbert Range group. This is a video in Manat (and to a lesser extent Tok Pisin) with subtitles available in Manat, Tok Pisin, and English (via CC):
https://www.youtube.com/watch?v=nh8Vuq1Hgqg