Looks good!
Only Library is usually just library since it's not a class.
You could also use in to replace one of the loops, which is not to say it's better, but easier (didn't try, but something like this):
for genre, books in library.items():
if book in books:
found = True
print ("Book:", book)
print ("Genre:", genre)
That will just check if the book is in the list.
(If you have a lot of books, this would be faster if you used sets instead of lists.)