I’ve always associated this word with the Chinese, and, although I had no idea of its roots, if pressed to the wall with a gun against my head I would have said it probably came from the Chinese. However, the true etymology takes us farther afield.
Here’s OED:
By some considered to be originally Tamil, and identical with the word kuli ‘hire, payment for occasional menial work’, whence (either by metonymy, or as short for kuli-karam ‘hire-man’, kuliyal, ‘hire-person’) kuli ‘hireling, labourer, man who does odd jobs’. The objection to this is that the first known mention of Coolies early in the 17th c. refers not to the Tamil country, in the south, but to the region of Gujarat, in the west of India. On this account there is reason to think the word identical with Kuli or Koli, the name of an aboriginal tribe of Gujarat (see sense 1), which is actually found spelt Koulli, Coolie in the middle of the 17th. c.
(The Kulis of Gujarat were well known to the Portuguese in the 16th c.; and these probably carried the name both to Southern India and to China (cf. 1745 in 2). It is probable that the similarity between Kuli and the Tamil word kuli ‘hire’ may have led to the use of coolie in Southern India in the sense of kuli-karam or kuliyal.)
First cite:
1554 BOTELHO Estado da India in Subsidios (Lisb. 1878) V. 155 E a Renda dos coles que s{amac}o pescadores ás estaquados ao mar, e per este Rio de Baçaím. transl. And the rent from the colés who are fishers at the stakes at the sea, and along this river of Bassein.
