What are the upload limits of your host?
You might need to increase via a server setting in the php.ini
With shared hosting, upload limits are usually quite low.
E.g.
Try increasing the following values in php.ini, for example:
memory_limit = 32M
upload_max_filesize = 24M
post_max_size = 32M
But check with your host's wiki on how to proceed (it varies from host to host...)
E.g. with Dreamhost: