Since the name of the Rhovanian Wizard Radagast actually is an Old Frankish (or perhaps Lombardic or Burgundian) form, as well as many Fallohide Hobbits, notably members of the Took family, have (latinized) Old Frankish, Lombard, and/or Burgundian names, it is likely that Tolkien imagined the Woodmen-tongue to be related to the other Northron tongues in a way as Old Frankish/Burgundian/Lombard was related to Anglo-Saxon, Old Norse, and Gothic (maybe these heavily latinized germanic names should reflect Dúnadan or elvish influence on the woodman-language).
While the -duk element clearly is derived from gothic 'tuggo (tongue) the Nahai- element seems obscure. It may be derived from Anglo-Saxon neah', so Nahaiduk would be the tongue of those who (are) near. The logical latinized Gothic form would be Neviatuggo. A possible Old Frankish form could be Nahotong or Nahotunga. Another possibility is that Nahaiduk is an original (untranslated) northron form closely akin to untranslated Westron terms such as Kuduk.
In LOTRO the Woodmen-tongue is represented by latinized Gothic.