Magento – Database Backup Not Working

I think this is more related to http://dba.stackexchange.com and has already been answered there quite often.

Take a look:

• How can I optimize a mysqldump of a large database?
• How can I backup a large SQL Server database without impacting performance?
• Best practices for backing up a MySQL DB

For a quick and easy solution where you could stick to mysqldump you could also try splitting your dump down to specific tables to reduce the size. Tables that don't change much or don't contain critical data don't have to be backed up that frequently: https://dba.stackexchange.com/questions/9306/how-do-you-mysqldump-specific-tables

the folder has always been var/backups.
See the method Mage_Backup_Helper_Data::getBackupsDir()

public function getBackupsDir()
{
    return Mage::getBaseDir('var') . DS . 'backups';
}

it's there in 1.9 and it has been there since the backup module was introduced.

Make sure the folder is writeable and you have enough disk space.

[EDIT]
I was half right in my original answer.
I assumed that Mage::getBaseDir('var') always returns MAGENTO_ROOT/var but that's not always true.
Take a look at the method: Mage_Core_Model_Config_Options::getVarDir() (this is called when determining the var dir).

public function getVarDir()
{
    //$dir = $this->getDataSetDefault('var_dir', $this->getBaseDir().DS.'var');
    $dir = isset($this->_data['var_dir']) ? $this->_data['var_dir']
        : $this->_data['base_dir'] . DS . self::VAR_DIRECTORY;
    if (!$this->createDirIfNotExists($dir)) {
        $dir = $this->getSysTmpDir().DS.'magento'.DS.'var';
        if (!$this->createDirIfNotExists($dir)) {
            throw new Mage_Core_Exception('Unable to find writable var_dir');
        }
    }
    return $dir;
}

If the var folder cannot be created magento uses as var dir the system tmp folder and creates magento/var inside it.
So for linux that should be /tmp/magento/var.
Take a look in there, maybe you will find your missing backups.