From the entry of 精選版日本国語大辞典:
So the word form is attested at least since late 19th century.
As you said, this is a combination of あら + まあ. あら can be traced back to the 10th century and まあ to the 18th century with basically the same meaning as in today (interjection of amazement).
In Japanese, phonetic equivalence is generally a very poor predictor of common etymology. Japanese is well known as having a preponderance of homophones, mostly due to the accretion of possible readings for each kanji which has developed over the centuries. But even among wago (和語), verbs ending in 'eru' are extremely common. Still, it is always worth ...
The "popular theory" linked from the question suggests both that the Japanese expression may have come from the Malay, or that the Malay expression may have come from from the Japanese.
The Japanese あらまあ (ara mā)
Broccoli's answer covers the Japanese. In short: あらまあ is purely Japanese, composed of purely Japanese elements and formulated in a purely ...