How to add a user/login Link to the Maintenance Mode page?
Yes, you should be able to. You can create a maintenance page template similar to any other in Drupal, "maintenance-page.tpl.php". However, to get that to work you probably have to make some changes to your template.php file. 

More info can be found here: http://adaptivethemes.com/how-to-theme-the-user-login-page-in-maintenance-mode although I believe that example is from Drupal 6, but the idea should be fairly similar for Drupal 7 as well.