I think you are on the right track. The first step in fixing a problem is to acknowledge that there is a problem. You have done that and have had a discussion with your boss. I will suggest you also have a discussion with your subordinates and get their feedback as well. Once you have all the inputs, create a plan of action as to how you plan to address those issues and give regular updates to your manager.
15 months is a long time for a Head of department to perform. You need to assess is how secure your job is. And that may not depend on your boss alone. Its hard for us to assess correctly, but depending upon how you did, company may already be thinking about asking you to go. Some organizations have a accommodating culture, where as some may think its best to let you go. If the organization is willing to invest in you, its worth staying. If its not, then its best to look for another job.
If you are certain that organization is willing to invest in you the next best thing would be to look for a smaller department where your skills could be used. One way could be that you suggest to your manager to swap you with another (possibly smaller department ) head. Your manager may have thought about something, ask him what that is. See if you are open to take one role below your current role. Also explore if there is some individual contributor role ( may be like account management in IT) where you could fit in.
It is also not a bad idea to look at this opportunity to switch tracks if you are interested. A few of my friends moved from technology to HR. You could look at some other function. All depends on what your manager has in mind and what you are open to doing.
A few organizations have internal job portal. If you have such a thing, then please go ahead and see what all openings are available. If its not so, see if you have friends in HR who could help you with the list of vacancies company is looking to hire for, and if anything is suitable to your role. It is always better to apply for those vacancies. Its cheaper for organization as well to transfer an existing candidate.
Also, don't loose heart. Everyone makes mistakes. It takes courage to admit you made one and even more wisdom to try and fix them. Most people are busy defending themselves. If you improve yourself, organization will be very happy to continue with you. If it doesn't work out here, some organization will love to have you. World is full of people who boast what they have done. Very few people have the courage to admit they made a mistake and learned from it. :)