Kdenlive relies on the MLT video engine.
By default, MLT only handles DV.
To have access to a wide variety of formats, you will need to install codecs.
Installed the audio and video packages listes on the following page:
On some systems, you may need to install the package names 'ffmpeg-unstripped' instead of 'ffmpeg'.