Do translation functions like __e() have to take strings in English in themes?

Yes, you can use any language you want. But if you want your theme to be translated by everyone, you should pick a language that people are likely to know, like English.

If you, for example, care only about former USSR countries, Russian might be as good.