Try
public OleDbConnection Connection = new OleDbConnection("Provider=Microsoft.Jet.OleDb.4.0;Data Source=" + Application.StartupPath + "\\Database.mdb;" + "Jet OLEDB:Database Password=123456;");
Note the semi-colon inside the quotation marks.
If that doesn't work then make sure your password is less than 14 characters as that can have an impact.
If that doesn't work, make sure you are using the correct driver - try
public OleDbConnection Connection = new OleDbConnection("Microsoft.ACE.OLEDB.12.0;Data Source=" + Application.StartupPath + "\\Database.mdb;" + "Jet OLEDB:Database Password=123456;");
You might also want to consider upgrading your Access database(s) to .accdb as .mdb is slated for retirement