The origin of the term is disputed and unknown; possibly a loanword from the Ruanruan language. According to Vovin (2007, 2010) the term comes from qaγan (meaning emperor or supreme ruler) and was later used in several languages, especially in Turkic and Mongolic.
Turkic and Para-Mongolic origin has been suggested by a number of scholars including Ramstedt, Shiratori, Sinor and Doerfer, and was reportedly first used by the Xianbei.
According to Vovin, the word *qa-qan "great-qan" (*qa- for "great" or "supreme") is of non-Altaic origin, but instead linked to Yeniseian *qε> "big" or "great". The origin of qan itself is harder according to Vovin. He says that the origin for the word qan is not found in any reconstructed proto-language and was used widely by Turkic, Mongolic, Chinese and Korean people with variations from kan, qan, han and hwan. A relation exists possibly to the Yeniseian words *qij or *qaj meaning "ruler". 
It maybe impossible to prove the ultimate origin of the title, but Vovin says: "Thus, it seems to be quite likely that the ultimate source of both qaγan and qan can be traced back to Xiong-nu and Yeniseian".