Lambda is something new. It's akin to BaaS (backend-as-a-service, like Parse or Firebase), but operates fairly differently from them, and doesn't have the mobile focus. Not sure if I'd lump it under BaaS or if it's an entirely new category (EaaS, execution-as-a-service?).
The interface to the outside world is different, the granularity of abstraction is different, and the pricing model is different. All those make it suitable for different applications, which indicates it's a new market and not going after the same customers as a PaaS.
AppEngine still treats your whole codebase as an "app" - all your handlers share configuration, they share a data store, and you interact with them over straight HTTP or XMPP. You're billed per instance-hour, which implies instances (virtual machines), and the control panel is setup to scale the number of instances devoted to your app.
Lambda is just a collection of functions, and you setup those functions to be triggered on various events. Those events could include HTTP requests to an API gateway, but they also include S3 or DynamoDB writes, Cloudwatch monitoring, SNS, and a wide variety of other apps. You're billed only for computing time; having an Amazon Lambda function uploaded that's doing nothing costs you nothing.
I get the sense that Amazon Lambda : database triggers :: Google AppEngine : webapps. The former is utility code that glues together events in multiple storage systems; the latter is designed to serve a single application and interface with all of its data needs.
You can pair Lambda up with AWS API Gateway and get something pretty close to App Engine. What sets Lambda apart is that it is event activated, similar to stored procedures in a database. But instead of updates or inserts to tables, Lambda can be triggered by events in other AWS services (S3 object created, API gateway method requested, etc).
