Термины родства, а также термины, обозначающие титул, социальное положение, выражающие почтительное отношение при обращении и под. (ага, бей, бек, бен, гызы, заде, паша и др.) в восточных именах пишутся строчными: легенда о Коркыт-ата.

Если речь идёт о самостоятельном имени Ата, то оно склоняется как существительное первого склонения: Аты, Ате, Ату, Атой, об Ате.
Если же это компонент имени -ата, тогда он не изменяется: легенда о Коркыт-ата.

Да, по-русски правильно: Алма-Ата. Эта форма закрепилась в русском языке, несмотря на то что по сути своей она ошибочна. История названия города такова: в 1854 году в урочище Алматы (в переводе с казахского 'яблочное') заложено укрепление, первоначально названное Заилийское, но вскоре получившее название Верное; позднее город Верный. В 1921 г. городу было решено вернуть национальное название, но вместо правильной формы Алматы в качестве официальной ошибочно принята форма Алма-Ата, где алма 'яблоко', ата 'отец'. Сейчас в Казахстане название города употребляется в форме Алматы, но в русском языке по-прежнему используется форма Алма-Ата.

Однозначного ответа нет. Приставка "а" есть в греческом языке, из которого заимствовано (целиком) слово атеист.  С точки зрения синхронного (современного) словообразования приставка не вычленяется. При этом морфемные словари выделяют  в этом слове приставку и суффикс:  а/те/и'ст/.