As long as you consider full loss of history to be no issue, the approach suggested by Ajay is perfectly valid. But in case you want to maintain the history of your shallow clone I have a different suggestion.
This means we can use a combination of a graft point and git filter-branch (as suggested in the linked question). However you have to note that this will rewrite your full history, making the new one incompatible with the remote we initially cloned from. Due to this, we should remove the old remote from our repository.
git remote remove <old-remote-name>
Now we can start our rewrite. Let's assume that we want to make the current master commit the new root for the repository.
This will rewrite the full history of our repository, with the current master commit as the new root. You can finalize the rewrite by removing the "backup" references in refs/original. Furthermore you can now delete the .git/shallow file.
After you've done this, you should be able to push the now ungrafted history in your new remote.
mkdir -p /tmp/git-copy
cd /tmp/git-copy
# create another copy of your repository
git clone file:///path/to/cloned/repo
cd repo
git rebase -i (first-commit)
# in vim:
# :2,$s/^pick/squash
# :w
# Now wait, it will take a while...
git push --mirror git@github.com:username/new-repo.git
I tried it just now on this repository. Seems to work - no history and all submodules are intact.
