How can I add a page layout to Mage_Page module?

Create a module with a dependency on Mage_Page and add the new layout in your own config:

app/etc/modules/My_Layout.xml

<?xml version="1.0"?>
<config>
    <modules>
        <My_Layout>
            <active>true</active>
            <codePool>local</codePool>
            <depends>
                <Mage_Page />
            </depends>
        </My_Layout>
    </modules>
</config>

app/code/local/My/Layout/etc/config.xml

<?xml version="1.0"?>
<config>
    <modules>
        <My_Layout>
            <version>1.0.0</version>
        </My_Layout>
    </modules>
    <global>
        <page>
            <layouts>
                <my_layout module="page" translate="label">
                    <label>My Layout</label>
                    <template>page/mylayout.phtml</template>
                    <layout_handle>my_layout</layout_handle>
                </my_layout>
            </layouts>
        </page>
    </global>
    <frontend>
        <layout>
            <updates>
                <my_layout module="My_Layout">
                    <file>my_layout.xml</file>
                </my_layout>
            </updates>
        </layout>
    </frontend>
</config>

app/design/frontend/base/default/layout/my_layout.xml

<?xml version="1.0"?>
<layout version="0.1.0">
    <my_layout translate="label">
        <label>All My Layout Pages</label>
        <reference name="root">
            <action method="setTemplate"><template>page/mylayout.phtml</template></action>
            <!-- Mark root page block that template is applied -->
            <action method="setIsHandle"><applied>1</applied></action>
        </reference>
    </my_layout>
</layout>