Here, Eleuteria happens to be right and it is actually cognate. See here for an etymological tree of the reconstructed Proto-Turkic root *kut:
https://starlingdb.org/cgi-bin/response.cgi?single=1&basename=%2fdata%2falt%2fturcet&text_number=1002. The listed form for Tatar is 'qot', but in the southern dialect of Crimean Tatar the /q/ sound becomes /x/, thus making it the exact sound we are looking for (source:
https://en.wikipedia.org/wiki/Crimean_Tatar_language#Consonants).
The 'lu' part is a Turkic adjective-forming particle. Therefore, the meaning of this name is roughly "fortunate bey (chieftain)".