The Dunlendings, or people of Dunland in the Third Age, were ultimately descended from the same ancestors as the Second House of the Edain - the Haladin, or Folk of Haleth. They shared the dark hair and, apparently, 'swarthy' skin of their distant relatives, and like those relatives, lived (at least initially) in close contact with the Druedain. Over time, the Dunlendings were driven west by the advance of Gondor, while the Druedain were isolated in their wood and became the Woses.
Of the Dunlending language - insofar as they had one besides Westron - we know one word: forgoil, 'straw-heads'. We also have one name in the language of the Woses - Ghan-buri-Ghan - which may be said to be distantly related... but several millennia separated. Then we have the language of the Haladin, even further separated in time.
But (and it's a big but), we also have the story 'Tal-elmar', which takes place in the lands of the Dunlendings at the time the Numenoreans first returned to the area - in the middle of the Second Age, or right in between our two samples. While neither 'Tal-elmar' or the Haladin give us much more than names, we can at least work out the basic phonemes of Dunlending - enough, that is, to potentially invent names.
Haladin Words & Elements
Haladin
-(d)in as a collective plural
Haldad - apparently this meant 'watchdog', from 'hal(a)', 'guard'.
Haleth
Haldar
Haldan
Halmir
Haldir
Handir
Brandir - while clearly derived from his father's name, the 'brand' element is apparently Elvish
Beldis - this appears to be Sindarin as well; apparently her brother was named Brandir, suggesting an elvish-named family.
Hareth. This name means 'Lady', and appears in the name 'Tūr Haretha' - the Mannish name of Haudh-en-Arwen, 'the Ladybarrow'. That name also suggests a genetive -a, and of course the word 'Tūr' - a word that also appears in Rohirric, but there meaning 'people'.
Halad, 'Warden', the title of the Lord of Brethil, and from it 'Obel Halad', though 'Obel' is Sindarin gobel, 'fort'.
Hundar
Hunleth
Hundad
Hardang
Meleth
Agathor
Hunthor
Manthor
Dorcas
Sargoth
Forhend
Avranc
'Tal-elmar' Words & Elements
Hazad Longbeard (who has seventeen sons - a good thing, apparently - and a five-foot beard)
Tal-elmar Flint-eye, his son (and the nickname is not a translation)
Buldar, father of Hazad
A battle at 'Ishmalog', against the Numenoreans
Elmar, Numenorean forced wife of Buldar. It doesn't say whether 'Elmar' is her original name, or the name given to her after her capture. There's a very dubious hint later that it might mean 'Slave' in the local language.
'The Swans of Godbelgod', which is corrected from 'Dur nor-Belgoth'. The latter name looks almost Sindarin.
'Go-hilleg' as a name for the Numenoreans.
Mogru, Master of the Hills of Agar, the local chieftain.
Patronymics! 'Hazad uBuldar, Tal-elmar uHazad'
A village named Udul
Druedanic Word
Ghan-buri-Ghan, with the element buri, 'son of'.
The 'u-' patronymic is very interesting - it shares a vowel with the Druedanic, but also strongly reminds us of the Khuzdul -ul. As previously discussed, the Haladin had a strong connection to the Dwarves - could this predate their entrance into Beleriand? The 'Tal-elmar' lexicon includes words that sound distinctly Dwarvish - 'Hazad', 'Udul', even 'Godbelgod' has overtones of 'Gabilgathol'. The swarthy Dunlendings could easily have had extended contact with Durin's Folk in Khazad-Dum, and absorbed parts of their language. There is even a suffix -u which means 'of' - precisely the meaning of our patronymic.
The name 'Hazad' is of particular interest, since it contains the common 'ha-' beginning from the Haladin. We know of this in the context 'hal', 'hand', and 'har' - the latter suggesting a woman, but in the story, Hazad is said to take after his mother. Since 'z' is a voiced alveolar sibilant, tracing it back to 'n' (the voiced alveolar nasal) seems most likely. This would suggest a shift nd > z.
'Gohilleg' as a name for a people is interesting, particularly when contrasted with 'forgoil' - and 'haladin'. The '-i-' element is common to all three, though it occurs with an -n in Haladin, -l in Dunlending, and in the middle of the word in Tal-elmar. Even more interesting is the 'gohil' element, which feels very close to '-goil'. Could we be looking at a 'go-il' construction? That would strongly suggest 'go' to be 'head' - Numenoreans were tall, but not blond, so 'straw' would be unlikely - and a '-il' plural formation. It also suggests the general loss of soft sounds such as h from Dunlending - so perhaps 'Hazad' would become simply 'Azad'.
Equally, the shift from the beginning to the end of our 'goil' might suggest a general such shift - pushing our patronymic to the end of the word as well. This would bring it more in line with the Khuzdul, which the loss of 'h' also reflects.
The name 'Buldar' could almost be Haradrim - see 'Hundar' and 'Haldir' - which suggests a very strong continuity of the -ar ending. If 'Elmar' is indeed a Mannish word, we might even conjecture a shift '-ir' or '-or' > 'ar'. Since we know 'i' has remained constant in the plural ending, it is more likely that -or was the ending lost.
The name 'Mogru' is interesting; a vowel-ending is not a common sight in Haladin. Given the general shift towards more Dwarvish sounds, it could possibly represent the loss of the soft 'th', with or without an associated vowel shift to 'u'.
Conclusions
To create a Dunlending name from a Haladin one:
Alter 'nd' to 'z'.
Remove 'H'.
Shift 'o' to 'a' in the ending (maybe).
Lose 'th' and change the foregoing vowel to 'u'.
Add the ending '-u' as a patronymic.
Add a descriptive aftername, which may change throughout their life.
Some suggested Dunlending names:
Unar
Azar
Aldar
And some names for women:
Alu (from Haleth)
Aru (from Hareth - this could also be the word for 'woman', and suggest the ending of 'elm-ar', 'slave-woman')
And in general:
Use a plural ending -il
'go' = 'head'
'for' = 'straw'
'ala' = 'guard'
'tur' = 'hill'
'elm' = 'slave'
'aru' = 'woman'
So a woman of Dunland could be called Arutur Azaru Far-Sight, 'Guard-woman, child of Azar, far-sighted'.