The only video Allegro supports is FLI/FLIC which are super old, just like Allegro 4 and DOS.

AVI players for DOS (regardless of library support) are almost non-existent because AVI was way too CPU intensive for early computers running DOS--that is, if you could run AVI you were already in Windows.

There will be no turnkey "download a lib and go" solutions. FFMPEG does have a DOS port. You have two options and both will involve some work but will still be 100x less work than writing your own decoder.

FFMPEG for DOS loads almost every format ever: (even Interplay's Baldur's Gate intro videos natively)

https://sourceforge.net/projects/ffmpeg-x264-dos/

Then either use/adapt FFMPEG to 1) Play a video by itself using FFMPEG not Allegro then when its done, startup Allegro in the same program, or, do what they did in DOS days and have the "intro movie" a completely separate executable that runs first. (This was VERY common!) or 2) Adapt FFMPEG to give you frames, and convert/dump those frames to Allegro bitmaps with a converter function, and then display those frames timed correctly using an Allegro timer.

This is a very esoteric request for an old library on an old platform so there's simply not going to be many libraries floating around or people who have both the ability and energy to accomplish it.

What specs is the machine running DOS? Does it have a floating point unit? Does it have MMX/AVX media extensions? Have you tried changing the encoding of the MP4? (constant bitrate, variable bitrate, and constant quantization product/CQP)

The program "may" run well in DOS and the video you're giving it, or the CPU specs are just wrong so you may be able to tweak those and get that running.

The beauty of one way I described doesn't require porting at all! You simply use either a batch file, or, a 3rd program that runs:

intro.exe   (the intro movie player)

then:

game.exe (the actual game)

Many DOS games did this. One program running, then closing and loading the next instantly, will simply appear as a resolution switch black screen. And, if the intro video fades to black, and then the game fades in from black, on an LCD you won't likely even notice. (Whereas a CRT might have a characteristic "click" sound from changing the resolution and locking the frequency).

One game that does this exactly, off the top of my head, is Colonization, a early America version of Civilization. The intro is animated manually, not an encoded video, but the concept is the same. So if you download it you'll see the files.

It was also common knowledge back in the DOS days that you could "skip" and intro by simply running the main game file instead of the one that starts the intro first.

[edit] Ugh, now Colonization is on GOG so all the abandonware sites deleted it.

[edit] For Spacewrecked 14 Billion Light Years From Earth
there is:

jmain.exe   -- the actual game
jsub.exe    -- the intro video
spacefix.exe [might be a crack or something]

and a bunch of batch files:

install.bat
mg.bat
start.bat
space.bat

in space.bat

echo off
cls
jsub

:loop
if exist jmain.exe goto :load
echo Please insert disk #2
pause
goto :loop


:load
jmain


See how it loads the intro, and then tries to run the game [and if it couldn't fit because it's on another floppy, says insert floppy #2]. You also don't really have to name them EXEs to run them (to hide them from users) as far as I know.