It's hard to justify from a Theravada perspective. If you try to do that, I would reckon you'd be fudging it at best.
The way we justify their "existence" is complicated. Contrary to Konchog, I think what you mean is "textually did they exist?" I.E. they are not mentioned before a certain date long after the compilation of the tripitaka. As for the Pali being closest to the "actual words of the Buddha" or not...that seems like a sectarian can of worms that I think is irrelevant.
Dzongsar Khyentse Rinpoche says about the Heart Sutra "the buddha never spoke this with his mouth." The Mahayana sutras are an emanation of the Buddha, not a tape-recorded documentary. You could not go back with a video camera and record the delivery of the Avatamsaka Sutra or something--it's not a historical event. It's a psychic, mythopoeic, spiritual one.
In the view of the Madhyamika philosophy the Tibetan tradition is rooted in, things (all phenomena, let alone deities) are beyond existing, nonexistence, neither existing nor not existing, or both existing and not existing. So in practicing a deity you should not think it is a truly existing God out there somewhere, separate from yourself. Nor should you think it's just in your imagination.
I think the idea of a thoughtform can send you in the right direction. http://en.wikipedia.org/wiki/Tulpa
These two deities you're asking about are not Tulpas, but it gives you the idea of how visualized deities are thought of in the Tibetan tradition: they are emanations with no inherent existence on their own. The appear solely as a skillful means to liberate sentient beings from delusion. They are in no way separate from the Tathagata, or seen alternately, they are Tathagatas in their own right who have emanated into our world through the teachings and blessings of Buddha Shakyamuni.
Furthermore you can think of Avalokitesvara the embodiment of the compassion (maha karuna) of the Buddha. He does exist in Theravada art of Sri Lanka, I know that for certain--he's just seen as the kind of pretty arm-candy of the Buddha along with Manjusri, and the arhats are considered the true heirs of the Buddha's teaching.
Dzongsar Khyentse Rinpoche says all of Buddhist practice is just a trick. It's an endlessly elaborate or singularly simple, depending on what you wish, but it's just a trick. The teachings are all deceptive because of our own delusion; once we realize, the tricks disappear. The vehicle is abandoned. We're done.
These two deities are some of the best tricks in the Vajrayana.