Can my current regime still be classified as HIIT?
Yes, most definitely.
The time intervals you're using are short enough and the numbers you posted make it sound like you're doing very well so far.
What is an effective way of gradually increasing the intensity of the overall workout?
You have a few options...
Option 1 - Gradually increase intensity overall:
You can continue with the same intensity for each round like you have been. Just increase the speed of the high speed legs when they start to get too easy. When I kick up a notch I usually do it in 1/2 mi/hr increments which would be a little less than 1km/hr for you. You should still continue to see benefits as you increase and adapt because it'll keep forcing your V02 MAX and anaerobic threshold to increase as you push harder.
The downside to this plan is, you probably have some good days where you run really well and some bad where you don't really run as well; especially as the workouts start to become a lot more difficult. A more dynamic plan will enable you to adjust to always be pushing your maximum.
The pattern for this workout would be:
6k 13k 6k 13k 6k 13k 6k 13k 6k ...
And the high intensity length (13k) would increase by 1k the next workout if you feel like you need to push more.
Option 2 - Increase until you break:
Start below your current maximum and gradually increase beyond. What I mean is, if you're 13km/hr max now, start at 10 (or lower) and for each round of high intensity increase the speed 1km/hr. Keep increasing until you hit your real maximum (when you don't see yourself doing another high intensity round any faster) then decrease at the same rate until you reach cool down.
The benefit of this pattern is, you'll be pushing your maximum during every workout. So, some days you'll hit 16k/hr others you'll only reach 13k/hr. You push based on how much you can handle. This becomes more important as you reach the absolute maximum you can do.
Because of the length of your workouts (45 min is a lot for HIIT) you could probably do your whole warm-up and cooldown using this. Ie, start at 6k/hr, increase to max, cool back down to 6k.
The pattern for this workout is:
10k 6k 11k 6k 12k 6k 13k 6k 14k 6k 15k 6k 16k 6k 15k 6k 14k 6k 13k 6k 12k 6k 11k 6k 10k 6k
The really hard part about this workout is the round right after you reach your max. It takes a lot of discipline to stick to the routine because the max will take a lot out of you. If that isn't challenge enough for you, I don't know what is...
Try it this out and see how it works for you. You could probably even develop one where you peak multiple times during the workout and increase/decrease at a faster rate.
...by how much should I be 'upping' the average speed and how frequently?
Up the intervals based on what you can handle. Based on how much you've done so far you should have a pretty good idea on how to gauge the intensity. Keep in mind that it won't be the same every day. You'll have good days and bad days. Listen to what your body tells you and adjust to compensate.
It may also help to get a heart monitor so you can accurately measure the load the workout puts on your heart. HIIT is all about increasing your V02 MAX and anaerobic threshold (how effectively your body uses oxygen). Measuring and targeting your pace to specific heart ranges may be a better way to set your pace than arbitrary speed measurements.
Or should I only be 'upping' the speed of the running part, keeping the cooldown intervals at a walk
Don't increase your low intensity intervals to be much more than 6km/hr. If you do, it'll start to rob you of your recovery between intervals. If you want more of a challenge, just increase the intensity of the high intensity intervals.
Should I be tweaking the time intervals?
I'm pretty sure I already covered this topic in depth.
I hope that helps. The concept is pretty simple. As the intensity gets more difficult to increase, you just need to mold the workouts to increase (or decrease) based on what you're capable of doing. You'll hit hard limits and plateau at some point. Whether you want to continue to push depends on what you're goals are.