Neccessary to call add_submenu_page and add_menu_page from admin_menu hook?

I am not sure how are you ending up with these results. The earliest hook it should work at is roughly admin_init. Anything as early as load process (wp-settings.php, including function.php, plugins_loaded, and even init) should (and does in my installation) produce fatal error, because function definitions hadn’t loaded yet.

The definition for these functions (wp-admin/includes/plugin.php) are only loaded after bulkd of core load (wp-load.php) is done.

In a nutshell documentation is correct and it’s a mystery why it works in your case. It shouldn’t, short of exotically customized core load process.