Tb podrías trabajar con una capa que te haga de margen izquierdo y que tenga un width en %
Código HTML:
<!DOCTYPE html>
<html>
<head>
<meta charset="iso-8859-1" />
<meta name="lang" content="es" />
<meta name="generator" content="editplus"/>
</head>
<body style="margin:0">
<div style="max-width:100%;width:100%;background:black;padding-top:10px;padding-bottom:10px;overflow:auto;">
<div style="float:right;min-width:10%;width:10%;;max-width:10%;background:black;display:block;">
</div>
<div style="float:right;padding-right:20px;color:#ffffff">
<a style="float:left;margin-left:10px;">menu1</a>
<a style="float:left;margin-left:10px;">menu2</a>
<a style="float:left;margin-left:10px;">menu3</a>
<a style="float:left;margin-left:10px;">menu4</a>
<a style="float:left;margin-left:10px;">menu5</a>
</div>
</div>
<div style="min-height:300px;height:300px">
</div>
<div style="position:fixed;bottom:0px;left:0px;max-height:28px;max-width:100%;width:100%;background:white;padding-top:10px;padding-bottom:10px;;">
<div style="float:right;min-width:10%;width:10%;;max-width:10%;background:black;display:block;padding-top:10px;padding-bottom:10px;">
</div>
<div style="float:right;padding-right:20px;color:#ffffff;background:black;padding-top:10px;padding-bottom:10px;">
<a style="float:left;margin-left:10px;">menu1</a>
<a style="float:left;margin-left:10px;">menu2</a>
<a style="float:left;margin-left:10px;">menu3</a>
<a style="float:left;margin-left:10px;">menu4</a>
<a style="float:left;margin-left:10px;">menu5</a>
</div>
</div>
</body>
</html>
saludos.