How people could make recommendations about ""switching up your program"" this early in the process is beyond me.....we don't have enough information to make that kind of recommendation.
First, what should be addressed is that muscle soreness in and of itself is not necessary if you're looking to lose weight. Everyone reacts differently to stimulus, but in my experience you should absolutely have some noticeable tightness/soreness from an effective workout that will hit ~24-48 hours after the session - but feeling like DEATH after every workout can be just as counter-productive.
Secondly, there could be multiple reasons why you aren't getting sore. Perhaps your workout is so varied that you aren't doing enough for each muscle to get sore, or perhaps the weights that you're using are too light for you. I was a trainer for years and most people suffer from both of those issues - they go to the gym and just use the handful of exercises they are comfortable with and don't really push themselves hard enough. If you're doing 10-15 reps+ for every set, and you're never reaching the point of ""form failure"", you're not going to get the benefits you're looking for. More on that later...
While professional opinions can be mixed as to which is better, personally for someone new to exercising I think breaking up the muscle groups is better than hitting full body. By splitting the muscle groups you're allowing yourself to specify your training, get more comfortable with machines for each body group, you're going to get a better mind/muscle connection, and you won't be working sore muscles over and over.
For someone going to the gym 4X/week, a good split would be:
Day 1 - Back.
Day 2 - Chest and Shoulders
Day 3 - Legs
Day 4 - Arms
I recommend working out for 30-45 minutes at least with weight training, and then proceeding to cardio.
You should be training to ""form failure"" - this means you continue to lift the weight until your form becomes impaired, not until you absolutely hit the wall. Going too hard is very stressful to your central nervous system and also puts you in a position where you're more likely to become injured.
As a ""new lifter"" you should be looking at keeping most of your sets between 8-12 repetitions. This will allow you to become more comfortable with the form for the exercises - but after time you would want to get some sets in at higher weight/lower rep schemes such as 4-6 reps. Personally I never recommend nor do I practice doing ""1 Rep Max"" sets often - if I'm feeling good I may add some weight, but training this way too regularly can be counter-productive.
Most people don't workout hard enough. If you want any type of visual difference, you need to PUSH your body! YOU WILL NOT GET TOO BIG! Natural bodybuilders spend YEARS doing everything they can to add muscle, and they still can't grow as quickly as they want to! If you're not losing weight, do not make the ""I'm adding muscle"" excuse!
Your nutrition will play the largest role in whether or not you will be successful. YOU CANNOT OUT-TRAIN A BAD DIET!
Cut the carbs back with your carbohydrates coming mostly from vegetables and some fruit (1-2 servings, if you're looking to cut bodyfat eating more than that isn't necessary).
Up your protein sources, including some after the workout. You could use Whey protein if you're able to purchase that on top of quality foods.
Ditch the fats that you know you shouldn't have - cut back on cheese, no fried foods etc!
For most people, a 600 calorie workout can be TOUGH! However, if you're eating properly you could potentially burn 600 calories every single day through nutrition, and the workouts just become a bonus. For example, if it costs your body 2300 calories/day to operate and you only eat 1800, you will be burning 500 calories every day and 3000 every week. Once you add workouts on top of that, you're getting the results you want!
I always tell people - if you're not already losing some weight every week from your diet, adding a few workouts WILL NOT get you much better results.