Thanks all for your input. However, I think something may not have come across. The name: KILLS ENEMY AT NIGHT was a forename. The original holder did not have a surname. But in the process of Anglicisation, Kills Enemy At Night's children took it as a surname. Thus, in my opinion, it is a patronym, but am of the leaning of jim1, that such surnames do not fit into European categories and new categories should probably be created.
In England, for example, the surname, you will find people named like, Athelstan fil. Grimbald, where the forename was given at birth, maybe generically, or maybe in an attempt to transpose some characteristic associated with that name. However, with Amerindians, it seems most took new personal names during their life and, at least in my experience, they were taken due to an event, feat, or characteristic.
In England you will find surnames from characteristics and there are likely a few obscure ones from feats or events; and these people would be known like John la Bald, Richard la Small etc. Thus the forename would be given at birth and the surname would be adopted in life. Amerindians did not have surnames, but rather their birth names were replaced during their life with a new personal name. So whereas European forenames are not descriptive, Amerindians ones are.
Thus, it doesn't fit in with European naming conventions. Although it is strictly patronymic, I feel there is a need for some distinction in the case of such names.
I have also been thinking on the point jim1 makes on mythology/religion-related surnames. A lot of Amerindian names appear to have such names and although they could be classified as descriptive, I again think a new category is in order.
No doubt there are a number of new categories that could be found outside Europe. In India (Asia) I have found surnames for castes, which I would distinguish from clan surnames and also surnames for languages. In some cases, I have seen villages where almost everyone has the same surname derived from a language.
Some names I have had real problems putting into a category. For example I have come across a Burundi surname meaning 'Burundians kill'