TL;DR: An ‘aullay’ is a yali, a hybrid creature in Hindu mythology.
The description of the ‘aullay’ in The Sword in the Stone is a lightly edited quote from E. Cobham Brewer:
Aullay, a monster horse with an elephant’s trunk. The creature is as much bigger than an elephant as an elephant is larger than a sheep. King Baly of India rode on an aullay.
E. Cobham Brewer (1892). Character Sketches of Romance, Fiction and the Drama, volume 1, p. 83. New York: Selmar Hess.
Brewer’s description comes in turn from the notes to Robert Southey’s poem The Curse of Kehama:
The Aullay. This monster of Hindoo imagination is a horse with the trunk of an elephant, but bearing about the same proportion to the elephant in size, that the elephant itself does to a common sheep. In one of the prints to Mr Kindersley’s “Specimens of Hindoo Literature,” an aullay is represented taking up an elephant with his trunk.
Robert Southey (1810). The Curse of Kehama, p. 358. London: Longman.
Brewer’s claim that “King Baly of India rode on an aullay” also comes from the poem, which he quotes:
Through these wide portals oft had Baly* rode
Triumphant from his proud abode,
When, in his greatness, he bestrode
The Aullay, hugest of four-footed kind,
The Aullay-Horse, that in his force,
With elephantine trunk, could bind
And lift the elephant, and on the wind
Whirl him away, with sway and swing,
Even like a pebble from the practis’d sling.
* Bali or Mahabali, a king of the Asuras in Hindu mythology.
Southey, pp. 169–170.
As Southey indicates in his notes, he got the creature from Nathaniel Edward Kindersley, though the spelling ‘aullay’ seems to be Southey’s own invention:
The choultry*, which bears the name of Trimul-Naig†, one of the kings of Madura‡ (to whom
all these buildings are ascribed, but of the date of whose reign we have no authentic account) being composed entirely of granite, has suffered but little; it is constructed in a style of peculiar richness and grandeur, and while the whole forms a sculptured system of Hindoo mythology, its pillars, all varying from each other, exhibit specimens of architecture, so curious as to have induced me to present the reader with drawings from three of them. […]
The next side (fig. 2) of this pillar, presents to the spectator an elephant surmounted by two fanciful monsters, the highest and largest of which resembles a horse, with the trunk of an elephant. It is called by Hindoo poets the aulee, and is supposed to exceed the last mentioned animal as much in size as it is here represented.
* A pillared hall or mandapa; † Tirumala Nayaka; ‡ Madurai in southern India.
Nathaniel Edward Kindersley (1794). Specimens Of Hindoo Literature, pp. 331–334. London: W. Bulmer.
Here’s Kindersley’s figure 2. The ‘aulee’ is on the right-hand side of the pillar, standing on the back of an elephant and twining trunks with a smaller ‘aulee’, perhaps its child.
If I understand Kindersley’s description correctly, his ‘choultry’ is the ‘Thousand-Pillared Hall’, part of the Meenakshi Temple complex, and if you search Google Images for photos of the hall you will soon spot more ‘aulees’, for example.
Kindersley says of the aulee that it ‘resembles a horse’. But is that quite right? Looking closely at the figure, we can see that it has paws (not hooves) and a long fleshy tail with a small tuft on the end, resembling the tail of a lion (not the short tail with long hairs of a horse). So what we are looking at is a lion-elephant hybrid, that is, a yali. Kindersley’s spelling ‘aulee’ is surely his attempt to transcribe ‘yali’.