It can take quite a while to complete so I would prefer letting the installer tell you it can't complete the install, but if you do get to the point that you are ready to give up, I suggest entering the Lion Recovery mode again by holding down the Command-R keys after you restart the system just like you did previously. This time, choose the Disk Utility application from the menu so that you can verify that your hard disk is OK.
I suggest running the Verify disk option and also check the SMART status listed on the very first screen. It would also be a good idea to verify that the hard drive is formatted as a Mac OS Extended (Journaled) volume. If you are able to boot fromyour external drive then I would also suggest downloading an application called SMART Utility from Volitans software so that you can pull the detailed SMART (Self-Monitoring, Analysis, and Reporting Technology) log files from your hard drive to see if there is any indication that it is failing. I suggest doing this because you are receiving a 'verify failed' message without any further details regarding what failed. You can use the SMART Utility application in the demo mode.
http://www.volitans-software.com/smart_utility.php