"Update-Database" command fails with TimeOut exception

Alternatively script out the change by using

Update-Database -script

You can then take the script and run it using SQL Management Studio against the database.

Found solution by myself.

Since EF5 there is a new property CommandTimeout which is available from DbMigrationsConfiguration

internal sealed class MyMigrationConfiguration : DbMigrationsConfiguration<MyDbContext>
{
    public Configuration()
    {
        CommandTimeout = 10000; // migration timeout
    }
}