He is going through the most public and bitter divorce since Charles and Diana's, but Paul McCartney is determinedly upbeat. As he releases his most personal album yet, he talks to Simon Hattenstone about getting to grips with his troubles

Guardian

Today, he is more restrained. His hair is dyed a respectable brown, not the shocking maroon-black of yesteryear. He looks gaunt and pale. I ask what songs are on the Wurlitzer. "A bit of Glenn Miller, Hound Dog, All Shook Up, I'm In Love Again by Fats Domino, Friendly Persuasion by Pat Boone - a nice one, that." He doesn't play the Fats Domino song today.

McCartney is about to release his most personal album, and the rumour mill has been buzzing - it's his revenge on Mills, it's all about their split, and everything he's endured. In fact, the album is about everything but Heather. On Memory Almost Full, he revisits his childhood, his family, John, George and Ringo, Linda, he anticipates his own death and talks about how he would like to be remembered. If Memory Almost Full were a short film, it would feature a contented old man rocking in a chair on his porch, contemplating the past and the future.

He is sitting on his sofa, all chinos, bare feet and Make Poverty History bracelets, explaining the title. "The phrase Memory Almost Full came into mind, then I realised I'd seen it on a phone - you know, you must delete something." Is that how he's feeling about life? "Yeah, yeah, yeah," he almost sings, like a refrain from an old Beatles song. "You've put too much information in, so delete something and I can handle it. I thought that was quite symbolic of life." It was only when the album was coming together that he recognised there was a leitmotif. "It is like looking back through a photo album, but there's more, because when I'm looking at the snapshots, I'm saying, 'Did that really happen?' There's a sense of pinching myself that went through quite a few of the songs."

At times, he appears to argue with himself about how autobiographical the songs are. Take Mr Bellamy, which is about a man in a desperate situation - refusing to come down from the roof of his house because he's happier up there with "nobody here to spoil the view, interfere with my plans ... I like it up here without you" - newspapers have suggested this is about his state of mind. But that's too easy, he says - for starters, he began writing this album when he and Mills were happily married, and anyway, this is a character-led vignette, a Beatles-esque short story. A second later, he concedes that however impersonal a song appears to be, on a subconscious level there is always something of him in it. "The common denominator is me. Even if I try and write, 'Desmond and Molly had a barrow in the market place', inevitably I come through the song."

Titles are always the last things he thinks of, he says. He pauses. Except for Sgt Pepper - in that instance, the concept came before the songs. He says it so casually. At times you forget just what McCartney has achieved in his 64 years. It's hard to know where to start - he is in the Guinness Book Of Records as the most successful composer in popular music, with the most number one hits in the UK as a performer (21), and the most number ones in America as a writer (32); Yesterday is the most covered song in history, with more than 2,000 recorded versions; Mull Of Kintyre, recorded by Wings, the group he formed with his wife, Linda, after the Beatles, was Britain's biggest-selling single until it was overtaken by Band Aid's charity record (which also featured him). Then there is McCartney the businessman - his company, MPL Communications, owns the rights to more than 3,000 songs, including the entire Buddy Holly catalogue and musicals such as Guys & Dolls and Grease. In 2005, he earned £48.5m. Finally, there is McCartney the tabloid sensation - he is in the process of going through the most public and bitter divorce since Charles and Diana. Media gossips recently suggested that he had embarked on another relationship, with Sabrina Guinness, but the rumour was scotched by both parties.

His divorce will cost him tens, possibly hundreds of millions of pounds, and has already cost him his place in this year's Sunday Times rich list - with £725m, he fell from 65th richest person in the UK to 102nd. It has been estimated that Mills could get as much as £200m.

What has most often come through McCartney's music is his relentless positivity. Whenever faced by adversity, he has given the trademark Macca grin and said that everything's fine. Never more so than on Memory Almost Full. Where we might expect bile and regret, we have love and gratitude and an embracing of all things past - or, at least, most things past.

"I was just thinking, you know, it's so easy to moan when you're going through problems, but at the same time it's good to stop and think of the great stuff. So I'm still grateful for this, that and the other." One of the things he's most grateful for, he says, is having been loved.

Memory Almost Full, McCartney's 21st solo album, is the first record to be released on the new Starbucks label, Hear Music. While it will be available through all the traditional outlets, it will also be sold at Starbucks cafes - which means that on the first day of release it will be heard by the chain's 45 million daily customers. Another example of McCartney's business nous.

Despite the chaos of his domestic life, McCartney appears at peace with himself on this album, finally ready to embrace his achievements. "As time goes on, I get more and more comfortable about my past. When the Beatles finished, there was a very difficult time with Wings when I wanted to shun my past in order to get on with my future, and then, when Wings finished, I wanted to put that behind me. As time went on, I started to become much more comfortable, because it was like, 'Oh God, it's going to be really boring if I can't bathe in memories of the Beatles or of Wings or of knowing John when I was teenager, meeting George on a bus, meeting Linda for the first time."

It's strange that a man with such an easygoing image has tortured himself so often over his past. There have always been two distinct sides to McCartney, and the sweet sentimentalist has often been at odds with the ruthless winner.

I tell him it seemed crazy that he was too busy worrying about whether the songs were written by McCartney-Lennon rather than Lennon-McCartney actually to enjoy them. "No, that's all gone," he answers. But it was there, wasn't it? "It was there, but like everything, they get wildly exaggerated. I can wake up one morning and have a particular bee in my bonnet about something, but because you have such a media presence, it goes round the world as a massively important statement." Although this particular bee did buzz around his bonnet for decades.

If he's so worried about media distortion, why not keep his thoughts to himself? "Why? I don't see why I should." He likes saying what he thinks - even if that means he's stuck with it for ever. Talk, discovery, self-awareness, he says, it's all part of one's personal evolution. "At least, I am evolving, thank God. Peter Ustinov once said he enjoyed doing interviews because it let him know what he was thinking. It's like a therapy session."

Nowadays, when he tours, he feels at ease with his audience. "It's funny, a couple of American tours ago, I was singing Blackbird and I started to chat to the audience much more. I'm very confident like that now. I remembered stuff that I'd forgotten for 30 years in explaining it. I get a therapy session with the audience, and I go, 'Hold on, I remember what that came from, it was a Bach thing that George and I used to play'."

He gets up to fetch a guitar from beside the Wurlitzer and starts playing the Bach. "Is this in tune? Yes. So that's the Bach. See, that's the bastardisation of it, and then this is how it evolves into Blackbird." He plays beautifully to demonstrate the transition. It's easy to forget how much the latter-day Beatles were influenced by classical music. Since the 90s, McCartney has released four classical albums including Liverpool Oratorio, his collaboration with Carl Davis, and the beautiful Oratorio Ecce Cor Meum, for which he has just won a Brit award.

When he thinks of the Beatles today, he feels privileged. "Gratitude. See, there's that word again: 'Gratitude'," he says in self-conscious Liverpool-LA fusion. "There's only three other people that happened to in the history of the universe. And so that's pretty good going, y'know? We had some fantastic times, some rough times, but listening to it now, or singing it as I do, I look back on it and think it's pretty shit-hot. Pretty good stuff. I sing it so I get to review the lyric and the melody, and I think, 'Ooh, that was clever. That was pretty good for a 24-year-old, for a bunch of...' " He trails off.

Yes, he knows how fiercely they fought in the studio and out of it, and, yes, he knows how important that was to the creative process ("We didn't always agree, and you get the best work by not agreeing"), but somehow it now seems so idyllic. "I just have the fondest memories. It's a huge part of my life, the Beatles. It was what happened to me that made me different. When you look back on it, it's a very warm, rich experience. It was not all roses, but that's the funny thing about time - it becomes all roses."

McCartney once said he was scared of forgetting the faces of loved ones. His mother died when he was 14, and 10 years later he started to have trouble picturing her face. "I would think of her and I couldn't conjure up her face as easily, so I'd have to go to a photograph. And it's a weird feeling, you go, 'Oh God, time is marching on, time's healing, but I don't want it to heal that much.' You feel guilt."

Two years after Linda died in 1998, he told me that he still talked to her. And now? He looks embarrassed, and says that comment was misinterpreted. "I remember it got retranslated and reprinted and people used to say, 'Is it true you talk to Linda and John Lennon - I also mentioned talking to John. It's not really talking to them in a sense, but you think about people you loved. I think about my mum, my dad, about Linda, about John. I think about George now."

He grins. "Actually, that's just broken a dream I had last night. I dreamed about my cousin, Bert. He was great, he was young and vibrant, and I remember thinking in the dream this is amazing, I know you're no longer with us, Bert, but I was so happy in the dream to see him again. So in that way I'm revisiting, I'm talking to my loved ones, and meeting them again."

But there are things he doesn't want to revisit. His divorce from Mills has not only been horribly public and extended, it has also involved a series of leaked allegations about McCartney's behaviour. The model family man has been portrayed by Mills as selfish, self-obsessed and violent - she has alleged that he refused to allow her to use a bedpan to save her crawling to the lavatory on her one leg, that he discouraged her from breastfeeding their daughter, Beatrice, because he wanted her breasts to himself, that he was a drunken pot addict who had hit her in an alcoholic rage. Throughout, McCartney has not responded, except with a statement from his lawyers saying that he would be "defending these allegations vigorously and appropriately" in the divorce proceedings.

I keep thinking of something he said shortly after they became an item, when I asked him if he thought Linda and Heather would have got on. "I know they'd like each other because they have a lot of things in common, not on the surface so much. A spirit, a toughness of spirit. No person would ever put them down. Put them down at your risk."

Today, he looks so vulnerable, so traumatised by the break-up. I ask how he's feeling. The question feels euphemistic, and he knows it. "Pretty good. I'm going through great struggles, but I'm feeling pretty good. I have a lot of good support, particularly from my family. In difficult moments like this, it's when a loving family shines through." His children never liked Mills, and his marriage to her caused a family rift. Has the divorce brought them closer? "Yes, it has. We're pretty close, anyway, but when you go into something difficult, it does actually bring you closer together."

You know what people want to do to you at the moment, I say. No, he replies. And I reach over and give him a big hug. McCartney smiles. "People actually do that. I get a lorra that off people. I get people I don't even know saying, 'Look, mate'," and he gives himself a sympathetic pat on the arm. "A lot of people come up to you and offer their support. A lot of people have been through similar circumstances and feel they have to communicate it to you."

And he's not quite out of it yet?

"Oh no. Noooooooh." It is the longest, most painful "no". "I'm not at all. But, you know ... there is a tunnel and there is a light and I will get there, and meantime I really enjoy my work and my family. I see people worse off than me, so I can put it in perspective. There's a thing we always used to quote in the 60s when things were rough: 'I walked down a street and I cried because I had no shoes, then I saw a man with no feet.' " It was an Indian parable, and that is one of the lines I live by."

For a man who has prided himself on his ability to live a normal, private life, it must have been hard to see himself splashed over the front pages for all the wrong reasons. "There's only really one answer to the problem of massive press coverage - don't look. So I don't read it. It comes to me occasionally, it leaks through the cracks - people say to me, 'Oh, I'm sorry about that, mate', and you're thinking, 'About what?' I know there's all sorts of shit going on, but if I don't look at it, then it's better. It's like going through Disneyland and not looking."

He looks at me as if I'm going to cite every accusation. "Don't tell me. What I don't know won't hurt me."

Has any good come of his relationship with Mills? "I've talked to a lot of people about it - you do - and the great thing that everyone says is you want to look at the positive that's come out of it, and the real positive is my beautiful baby daughter. Both parents know that that is something great that came out of our marriage, even though the marriage didn't work out. I don't want to say any more than that in order to keep some dignity about the situation." Their daughter, Beatrice, is now three, and McCartney wants joint custody.

Is it true that he's now dating Sabrina Guinness? "There is absolutely no truth to any of the stories that have been printed. It's difficult to know what to do about it. In a few months I guess people will see for sure it was all just unfounded speculation."

He has prided himself on the way he has conducted his life openly, as part of the people. He sent his children to the local comprehensive, and he will always talk to fans. But if he's with family or not in the mood, he refuses photos and autographs. Often, he says, friends find that puzzling. "They say you spend more time chatting, you should just do their photos. I say, no, at least I'm in control when I'm chatting." And that hasn't changed over the past year? "No, people have been cool. I have a lot of faith in people.

"It's funny, today I was in the park having a coffee with my daughter [Stella] and her boy, having a great time feeding the ducks. It was lovely because there was no one around, no paparazzi, we were actually having a family private moment, and then there were a party of German student kids, and I could see a couple had spotted me, and they asked, 'Können wir ein Foto machen?' [Can we take a photo?] I said, 'Well, actually, this is a very private moment,' so I said hopefully you understand, and people always do, so they back off."

As I leave, he takes one of Beatrice's doodles from his trouser pocket. "Look at this," he says, every bit the proud father.

The week after we meet, McCartney's private family lunch in the park is featured in Hello! magazine - the paparazzi were out in force, after all. Around the same time, McCartney websites go crazy as it emerges that Memory Almost Full is an anagram of For My Soulmate LLM - the initials of Linda Louise McCartney. I call McCartney to ask him if it was intentional. "Some things are best left a mystery," he says.