Веле- (означає щось величне) та бая (легенда, міф).
міф
Прямий переклад.
Приклади вживання — 
goroh.pp.ua: Билинний
Кругла вежа бронепоїзда здавалася шапкою билинного витязя-богатиря. (О. Донченко)
І ліс якийсь картинний, і чагарі надто билинні, й птахи нетутешні. (О. Бердник)
Час уже нашому билинному богатиреві встати з правічної української фортеці-печі й почати рухатися. (з публіц. літ.)
Скупими й точними барвами змалював О. Гончар урочисту, билинну красу прадавнього українського степу. (із журн.)
Є докази, щоб звіритись?
В українському фольклорі немає билин. А якби й були, то слово мало б "у" після "б", а не "и".
Дієслово "бити" через "и" (а в деяких говірках і зі збереженим *y) ше досі живе в багатьох говірках. Чого його цуратися?
Та навіть у літературній мові в багатьох словах. Здобич, збиток.
Так, Ваша правда. Та билин у нас однаково немає.
