Ok, so it wasn't the wife But this is what I found on the internet:

- Никакого отношения к псевдониму Ленин женщина по имени Лена не имеет. Проблема решается просто. В 1900 году, когда Владимиру Ульянову необходимо было выехать за границу, он подал прошение на имя псковского губернатора о выдаче заграничного паспорта. Однако опасался, что из-за революционной деятельности паспорт не получит. Поэтому Надежда Константиновна обратилась к своей подруге по вечерней школе Ольге Николаевне Лениной. Та попросила своих братьев Сергея и Николая, которые знали Владимира Ульянова по Вольному экономическому обществу. Сергей во время командировки в Псков вручил Ульянову паспорт своего отца, Николая Егоровича Ленина. В паспорте была подделана дата рождения в соответствии с возрастом Ульянова. Правда, этим паспортом Владимиру Ульянову воспользоваться не пришлось: Николай Ленин был статским советником. В 1900 году Владимир Ульянов впервые употребил фамилию Ленин как псевдоним, чем-то она ему полюбилась; при жизни он этот псевдоним применил около 800 раз. А после смерти именем Ленина были названы города, поселки, улицы...

http://www.compromat.ru/main/lenin/evrei.htm

For those who are lazy: it says that since Vladimir had to go abroad and he was afraid that they won't allow him, because of his revolutionary activities, his wife (so there was a connection after all! Take that, DenisM! ) asked her friend with the name Olga Lenina for help, and Olga's brothers gave Vladimir their father's passport (with the name Lenin)