Yet more from Jones, Robert F. (ed.) "Annals of Astoria"

[Alan H. Hartley]

Most of the examples I've found from the first half of the 19th century
are in k-. The earliest is:

1805 Jrnls. Lewis & Clark Exped. VI. (1990) 112
Kil-la-mux nation reside to the South of the Columbia and in noumerous 3
V[illages].

Here's what I have on the etymology:

< Chinook t?ilimuks 'those of Nehalem Bay' < (i)t- (plural) + -qilim
'Nehalem' + -uks (also -iks, -aks; "animate" plural). Examples in k-
represent forms elicited without the initial t-, or may simply be
mishearings of t?- by early transcribers. (The locative prefix n- in the
toponym n?ilim 'Nehalem' is absent from the ethnonym.) [? = glottal
stop]

based on Hdbk. N. Amer. Indians VII. (1990) 566, and e-mails from Robert
Moore 2/26/99, Dell Hymes 2/26/99, and D. Robertson 12/30/98

Alan