I'm currently conducting a set of broad searches in both Medline and PsycINFO. However, when importing the results into my reference manager, I'm surprised of how little overlap there is between these two databases. That is, when importing a couple of thousand references from each database, both set of results retrieved using the exact same search terms, there's only a handful of duplicates (I'm using a fairly unrestrictive duplicate finding algorithm in EndNote, only looking at year and title of the article and ignoring punctation and spaces). This is, for example, the case if I search for (memory AND sex) and restrict the results to studies with human subjects.
Unfortunately, I'm not sure there's a quick answer to the exact amount of overlap, but you may be able to get an estimate by comparing the list of journals included in Medline (http://www.nlm.nih.gov/archive/20130415/tsd/serials/lji.html.notice.html) to the list of journals covered by PsycINFO (http://www.apa.org/pubs/databases/psycinfo/coverage.aspx). Also, keep in mind that each database has it's own thesaurus and preferred search terms, and the terms you're using might pull up different results in different databases. You may be able to optimize your results by using search terms specific to each database.