Hmm....well from my experience of last fall through the winter even though I was "working out" it turned out I wasn't really at the intensity it should have been. I was also eating not great but that's not your issue but maybe you are eating more then is needed.

What are you doing for your workouts? Are you pushing yourself? If you are pushing yourself with your lifting maybe you need to drop 1 day and only do 3. You should have at least 1 day between lifting sessions so your muscles can recover.

How do you eat your calories? Do you go up and down each day depending on your workouts or do you eat a constant everyday? I've calculated my exercise into my daily calorie goal and eat a constant each day so it becomes more of weekly goals vs. daily. I find it less stressful.

I just took a closer look at your diary. It looks like a couple months ago you were averaging low calories....like around 1200, if that, and in the last month you've been on the higher side.

Maybe try doing a consistant daily intake of like 1750 and if you aren't really pushing yourself with your workouts up your intensity a little bit. Are you a gym member? If so do they have personal trainers? If you have the means I would highly recommend one. It was the best descision I made.

The high fat doesn't matter unless you are eating over maintenance - but it appears you are eating at maintenance or TDEE.

So I'd suggest you have already done this to yourself with that routine. And you want to do exactly what it says to keep losing.
http://www.t-nation.com/diet-fat-loss/truth-about-metabolic-damage

I'd second the thought that now your workouts aren't what they could be, even though it may feel like you are doing the same. When you lost weight, then the pace for running should be faster to equal the same intensity level, and the weight on the bar should have increased merely to be lifting the same amount (should be even faster and more yet for improved technique).

Since you seem to be of the thought that bigger is better (eat less, exercise more, increase the deficit, though there isn't one right now), you could follow this out to the end.

Since current eating level with current level of exercise is maintenance, you would need to decrease calories 250 and find an average of 250 more to burn daily to lose 1 lb weekly.

How successful will that be you think at that eating and exercise level.
For every 10 lbs lost, your maintenance or TDEE drops by about 75 cal. So near goal weight, it appears you'd need to eat even 150 less than that to keep losing 1 lb weekly.

And once you reach goal weight, your maintenance with doing that new level of workouts would be 400 less than current.
And be aware exercise stops have as much a positive results when you undereat so greatly from potential.

Can you really eat that much for maintenance?

And, if you don't workout that much - you'd actually have to eat even less.
You go on vacation and eat more and exercise less - you gain fat.
You get sick or injured and can't workout - you better eat a whole lot less or you gain fat.

Is that really the future you want? I see future failure written all over that.

Suck up the fact you put yourself here in a bad spot, and take some time and heal your body.

The fact your body is already stressed with disease means the stress of a diet and too much exercise is just not going to work for fat loss.

Perhaps you are of the thought all this exercise is for weight loss - very wrong.

Diet is for weight loss - done right only fat loss, done wrong includes muscle mass loss. That sucks later big time.
Exercise is for heart health and body improvements - done right can make diet easier because you get to eat more, done wrong can aid muscle loss actually.

Also, exercise if done right tears the body down.
It's the rest for recovery and repair that builds it back up, stronger if diet allows.

Pretty sure you've gotten to the point with terrible diet that exercise is now just one big stress on your body.
Doing paleo with low carbs and great amounts of exercise goes specifically against their recommendations - for a very good reason - it's a bad idea. Hence they reason they modify it for those that enjoy "killer" or "chronic" cardio.

So you ready to heal, or keep going this route that isn't working?

You know the definition of insanity, right?

Lifting full body 3 x weekly. Split routines are for intermediate lifters - you been doing lifting for 2 years to be intermediate?
Cardio running only after lifting, only walking on days between lifting to aid repair.

Since you run, you must know of the benefits of intervals.
Why are they useful?
What would you say happens if you went hard 30 seconds, followed by hard 30 sec, followed by hard 30 sec?
What happens to that hard effort very quickly?
What does the hard effort eventually become?
Look at your current workout schedule day by day, what is it like - true intervals, or my description above?