Hi,
Our Installbuilder for Qt product is a crossplatform installation tools that has a Qt frontend and is used by many commercial developers (including Trolltech itself for packaging their QtCreator IDE). Using 4.4 and compiling out the parts that we did not need, we got the overhead down to 4.1 Mb on Linux x86, 5.2M on Linux x64 and 5.3Mb on Windows. Take into account that this is before processing it with UPX. Also, if the same binary needs to support multiple Linux distributions, you may need to consider shipping libstdc++, which will add about 800kb to the size.
You will need to build your own versions, and basically enable / disable ifdef# for widgets that you do not use, image formats you do not need to support, etc. Although the Qt source code is already prepared for that, and there are some tools that should help, the reality is that it is a cumbersome manual process (but necessary for an app like ours). Their embedded version (formerly known as QTopia) and 'regular' Qt were merged into the same codebase, so I am sure moving forward it will be increasingly easier to build customized/trim down versions.