In Game of Thrones S06E04
Daenerys burns all the Dothraki Khals and then comes out of the burning house. Then all the Dothraki that came to see what was happening knelt before her, considering her the new leader of the horde because she 'defeated' the other Khals.
Why would she be considered a Khaleesi and not a witch? Why did the Dothraki decide to follow her? It's seems like witches are a bad thing in Westeros, Essos and especially in the Dothraki culture. In the eye of a Dothraki man, I feel like she should be seen as a witch for surviving/creating the fire. Also, there are probably a lot of Dothraki/Khalasars that probably don't want to be ruled by some foreign girl.
EDIT : I think the Dothraki in the show does not believe she is a witch because I think Dothraki would not follow a witch. Witches seem to be a very bad thing in the eyes of this culture (see how the Dothraki girls in S06E03 were saying that Daenerys was a witch and that they should kill her, and after the event of the season 1 also).
So, if you think that the Dothraki might think that she's a witch but decide to follow her nonetheless, why would they agree to follow a witch even though witches are known to be a bad thing in this culture?