However these names are not found [easily] in the Ramayana or Mahabharata texts.
How has this name become quite famous?
I read this and to me makes sense.
Hanuman is called Bajrang Bali. I tried to understand why he was so called. This name is being used mostly in Northern India and less in Southern India, indicating Lord Hanuman.
According to my understanding, the original word might be VAJRAANGABALI. If we split this word, we will get 3 words. VAJRA + ANGA + BALI.
A) VAJRA indicates 2 meanings.
It means THUNDERBOLT that we see during rainy season, indicating great celerity, power and effectiveness. That is why the weapon of Lord Indra is called VAJRAAYUDHA.
It means a DIAMOND, indicating here the person having the strength of diamond
B) ANGA means parts of body.
C) BALI means person having immense strength.
By understanding the meanings of 3 words together we will get a different meaning, i.e., a person having immense strength, celerity and effectiveness in his bodily parts equivalent to a THUNDERBOLT or a DIAMOND.
This name VAJRAANGABALI of Lord Hanuman might have got corrupted in the Eastern parts of India to Bajrang Bali.
The sound VA will be spelt in the Eastern parts of India as BA. For example: the name RAVINDRANATH TAGORE will be spelt as RABINDRANATH TAGORE.
Hanuman is very well known for his physical strength. The name Bajrang is acquired by Him due to this reason. There are numerous references to this strength in Valmiki Ramayana. Bajra is a cultural variation of Vajra. Anga means a body. Vajraanga means one with a body like the Vajra. Here, Vajra can be interpreted as strong and also as strong as the thunderbolt of Indra.
RamcharitManas by Gosvami Tulsidas is popular in the North Indian region. So, this name has become people due to usage in this epic. This name also appears in famous Hanuman Chalisa which is penned by the same author.
महावीर विक्रम बजरंगी।
कुमति निवार सुमति के संगी॥ ३ ॥
mahāvīra vikrama bajarangī।
kumati nivāra sumati ke sangī॥ 3 ॥
You are the great hero, you are endowed with valour, your body is as strong as Indra's Vajra. You are the destroyer of vile intellect, and you are the companion of one whose intellect is pure.
Translation from Wikipedia.
There is reference where Hanuman's body is compared with the vajra, the weapon of Indra. One in Bala kanda and other in Yuddha Kanda.
तम् आपतन्तम् उत्पत्य हनूमान् मारुत आत्मजः |
आजघान तदा मूर्ध्नि वज्र वेगेन मुष्टिना || ६-७०-२४
Then, Hanuma the foremost of monkeys, while jumping up, struck on the head of Devantaka rushing upon him with his fist equal to a thunder-bolt. [6-70-24].
Though other answers already explained why Hanuman is called Bajaranga Bali that is Hanuman's body is as strong as Indra's Vajra. So, Bajaranga stands for "Vajra + Agna".
I'm here adding verse from Valmiki Ramayana that declares the body of Hanumana is like Vajra:
मारुतस्य औरसः श्रीमान् हनुमान् नाम वानरः |
वज्र संहननोपेतो वैनतेय समः जवे || १-१७-१६
Sanskrit+Hindi translation according to Gita Press Book:
English translation from sacred-texts.com:
Hanúmán, best of monkey kind, Was son of him who breathes the wind: Like thunderbolt in frame was he, And swift as Garud's 4b self could flee.
English Translation from valmiki.iitk.ac.in:
Vayu, the windgod, begot a son named Hanuman, mighty and graceful, having a body as hard as a diamond and speed equal to Garuda's.
English translation from valmikiramayan.net:
The direct son of Air-god is the marvellous and adventurous Hanuma with an indestructible body, and one identical in the speed of lady Vinata's son, namely Garuda, the divine eagle vehicle of Vishnu