The database was working just fine and I was getting back-ups everytime I add new products. The dump databases used to be around 10-15 MBs. Now it goes up to 80-90 MBs and Administration > DB Management > Create new dump function does not work anymore. It keeps waiting for several minutes, then I get "Server error" message. When I check through the FTP I see that it stops at 50-60 MBs. I usually select "Create a table structure" and select all the tables just to make sure I do not miss anything. I tried to eleminate some tables but did not work properly. Does this take back-up of product images too?
Any suggestions?

Try to repair and optimize the database via phpmyadmin or with the server side database tool you are using and then try again.
 
Also changes in server configuration might be a cause, if there where changes.

DickS how can I do this through the phpMyAdmin?

Please do a Google search. One of the results:
 
http://php.about.com/od/mysqladministration/qt/repair_mysql.htm