The data provided in this answer is relevant to Telegram web and Android application Telegram X as of 10/06/2018.
Tl;DR - Video: Baseline 3.0 640x360 ~800 kbps VBR single pass Audio aac 128 VBR
While there is an official statement, it is outdated.
As the answer above stated: Telegram indeed uses H.264 and MPEG-4 is a must as a container.
If you upload a video file from computer, in the case the file exceeds 10 MB it will be marked as a
file and will not be playable by Web app or Android app. It still will be playable on iPhone however. Bitrate and resolution don't make any difference in that specific case.
When uploading a video file from the phone, unless you specifically choose to
upload as uncompressed file, which will disable playback, the Android application will encode your video for you (even if you used better encoding) to the following format:
Video: Baseline 3.0 640x360 ~800 VBR single pass
Audio aac 128 VBR
What can you do?
You can create a file on the pc, send it to yourself as a
file, and upload it to telegram using your phone.
As an example I can provide a video that was uploaded to Telegram using this method:
1:04:02, Main 3.1, 1280x720, 700 kbps VBR double pass, AAC 128 VBR total file size - 379 MB
After uploading to Telegram:
1:04:02, Baseline 3.0 640x360 798 kbps VBR (pressumably single pass), AAC 125 VBR, total file size - 424.2 MB
As a result, the video lost some quality and gained 11.87% to its size but is playable using the build in player which is neat, since it supports picture in picture.